A linked list is a data structure that contains a sequence of nodes such that each node contains a value and a pointer to the next node. The first node is referred to as head and the last node is referred to as tail.
If a list have nodes that contains only a reference to the next node it’s a singly linked list. A doubly linked list has nodes that have a reference to the next node and a reference to the previous node.
Arrays vs Linked lists
It’s useful to reason about linked lists in comparison to arrays. Both have advantages and disadvantages and you need to be able to fluently talk about pros and cons of using each. Here is a summary of runtime times of Arrays vs Lists:
Insertion
Array: O(n)
Singly-linked-List: O(1)
Doubly-linked-list: O(1)
Search
Array: O(n)
Singly-linked-List: O(n)
Doubly-linked-list: O(n)
Deletion
Array: O(n)
Singly-linked-List: O(1)
Doubly-linked-list: O(1)
In Java you can implement a list node like the following
public class ListNode<T> {
public T data;
public ListNode<T> next;
}
Basic operations on lists
Make sure to understand the intuition and to be able to write code for these flawlessly. It’s very important to be familiar with the solution to these problems because these are building blocks for all algorithms on linked lists.
Find the middle element of a list
Linked lists algorithms often use two pointers which progress at a different pace to iterate over the list. For instance if you want to find the middle element you can use 2 pointers such that at each iteration the slower pointer advances to the next element while the faster one advances by 2 elements. When the faster element reaches the end of the list the slower will be exactly in the middle.