Linked List
Three types of Linked List
- Singly Linked List
- Doubly Linked list
- Circular Linked List
Java Implementation of LinkedList
import java.util.LinkedList;
// Creating a LinkedList
LinkedList<String> linkedList = new LinkedList<>();
// Adding elements to the LinkedList
linkedList.add("Apple");
linkedList.add("Banana");
// Adding elements at specific positions
linkedList.add(2, "Grape");//Index 2
linkedList.addFirst("Apricot");// Start of tje LinkedList
linkedList.addLast("Fig");// End of the linked List
// Getting elements by index
String secondElement = linkedList.get(1);
// Removing elements
linkedList.remove("Banana");
linkedList.remove(3);
}
Singly Linked List
- Head is the starting point
- Can traverse only in one direction
- copy head into a runner and work with the runner. Never modify head
class Node<V> {
public V dataObject;
Node next;
}
Doubly Linked List
- Head is the starting point
- Can traverse only in either direction
- copy head into a runner and work with the runner. Never modify head
class Node<V> {
Node previous
public V dataObject;
Node next;
}
Array vs Linked List
for (int i = 0; i < arr.length; i++){
System.out.prinln(arr[i]);
}
for (ListNode runner = head; runner != null; runner = runner.next){
System.out.println(runner.data);
}
Singly LinkedList Challenges
Reaching the second last element and staying there
// Reaching the second last element and staying there
while(runner.next.next != null){
runner = runner.next;
}
Traversal accross all elements
Node runner = head;//head
while (runner != null){
// Obtain the dataObject and perform operation on it
runner = runner.next;
}
Add at the front of the List
head = new Node(value, head);