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)