What is a linked list
1) each element in a linked list is called a node.
2) It is similar to an array, each node in the linked list has the data part and a link to the next node.
3) linked lists have O(1) time complexity for insertion or deletion at the beginning i.e at position 0.
How to implement
-> Java has builtin LinkedList which you can import from the utility library
-> or you can implement your own LinkedList
Built-in LinkedList
LinkedList<String> x = new LinkedList<String>(); // to add elements to the list x.add("1"); // here the first element we added becomes the head x.add("2"); x.add("3"); x.add("4"); x.add("5"); x.remove("5"); // to traverse the linked list Iterator<String> i = x.iterator(); while(i.hasNext()){ System.out.print(i.next()+"->"); } implementing a LinkedList, my approach:
// LL stands for LinkedList public class LL { public Node head; public LL() { head = null; } public LL(int data) { head = new Node(data); } public void add(int data) { if (head != null) { head.appendToTail(data); } else { head = new Node(data); } } public void printList() { Node dummy = head; while (dummy != null) { System.out.print(dummy.data + "->"); dummy = dummy.next; } System.out.print("null"); } public void delete(int d) { Node newHead = new Node(0); newHead.next = head; Node previous = newHead; Node current = head; while (current != null) { if (current.data == d) { previous.next = current.next; } else { previous = current; } current = current.next; } head = newHead.next; } public class Node { Node next = null; int data; public Node(int data) { this.data = data; } void appendToTail(int d) { Node end = new Node(d); Node n = head; while (n.next != null) { n = n.next; } n.next = end; } } } Try out these challenges on LinkedList to get a good grasp
Top comments (0)