Linked List implementation in Java…
====================Node.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class Node { int key; Node link; public void setKey(int key) { this.key = key; } public int getKey() { return this.key; } public void setLink(Node node) { this.link = node; } public Node getLink() { return this.link; } public static Node createNode(int key, Node link) { Node node = new Node(); node.setKey(key); node.setLink(link); return node; } } |
======================LinkedList.java ===================
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
public class LinkedList { Node startNode; public LinkedList() { startNode = Node.createNode(-9999, null); } public void searchKey(int num) { Node node = startNode; int countPos = 0; while (true) { if (node.getKey() == num) { System.out.print("\nKey (" + num + ") at index " + countPos); return; } else { if (node.getLink() != null) { countPos++; node = node.getLink(); } else { System.out.print("\nKey (" + num + ") not found!!"); return; } } } } public void getKey(int index) { Node node = startNode; for (int i = 0; i < index; i++) { if (node.getLink() != null) { node = node.getLink(); } else { System.out.print("\nKey not found!"); return; } } System.out.print("\nkey found at index " + index + " is " + node.getKey()); } public void add(int num, int index) { Node node = startNode; for (int i = 0; i < index - 1; i++) { if (node.getLink() != null) { node = node.getLink(); } else { System.out.print("\nposition not acceptable"); return; } } Node newNode = Node.createNode(num, null); node.setLink(newNode); System.out.print("\nNode added successfully"); } public void deleteKey(int key) { Node prevNode = startNode; Node currNode = startNode.getLink(); if (currNode != null) { while (true) { if (currNode.getKey() == key) { Node tempNode = currNode.getLink(); prevNode.setLink(tempNode); currNode.setLink(null); currNode = null; System.out.print("\n Node with key (" + key + ") deleted successfully!"); return; } else if (currNode.getLink() != null) { currNode = currNode.getLink(); prevNode = prevNode.getLink(); } else if (currNode.getLink() == null) { if (currNode.getKey() == key) { currNode = null; } else { System.out.print("\nKey not found!!"); return; } } } } else { System.out.print("\nList is empty!!"); } } public void printList() { Node node = startNode; System.out.println(); while (true) { System.out.print(node.getKey() + "\t"); if (node.getLink() != null) { node = node.getLink(); } else { break; } } } public static void main(String args[]) { LinkedList linkedList = new LinkedList(); linkedList.add(0, 1); linkedList.printList(); linkedList.add(1, 2); linkedList.printList(); linkedList.add(3, 4); linkedList.printList(); linkedList.add(2, 3); linkedList.add(3, 4); linkedList.add(4, 5); linkedList.add(5, 6); linkedList.add(6, 7); linkedList.add(7, 8); linkedList.add(8, 9); linkedList.printList(); linkedList.getKey(1); linkedList.getKey(7); linkedList.getKey(9); linkedList.getKey(10); linkedList.printList(); linkedList.searchKey(2); linkedList.searchKey(5); linkedList.searchKey(9); linkedList.printList(); linkedList.deleteKey(4); linkedList.printList(); linkedList.deleteKey(8); linkedList.printList(); linkedList.deleteKey(0); linkedList.printList(); } } |
NOTE: LinkedList is also present as a concrete implementation in Java SDK as java.util.LinkedList