Author: Brandon Pearman

The views expressed here are mine alone and do not reflect the view of my employer.

Linked lists are extendable collections. Unlike an array, once a linked list has been created the elements can easily be added and removed while remaining memory efficient, ie the size of the list is flexible.

This is accomplished by each element having a reference to the next, therefore other elements can live anywhere in memory. The below linked list does not allocate memory for the maximum size of the list, you can simply add new items on.

A disadvantage of linked lists is that they are slow to search. This is because every element needs to be checked by following the chain of links. ie cant simply go to an index because the collection is not in predefined memory locations.

Linked List Example in memory

element 1: memory 100 and points to 264

element 2: memory 264 and points to 345

element 3: memory 345 and points to 569

element 4: memory 569 and points to null

This structure makes it harder to find elements because you have to traverse through each element.

Goto 1st element at 100 and find out where 2nd element is (264) =>

Goto 2nd element at 264 and find out where 3rd element is (345) =>

Goto 3rd element at 345 and find out where 4th element is (569) =>

Goto 4th element at 569

The benefit of this structure is that you can keep adding more references onto the end and extend the size of the linked list.

Singly Linked List

Circular Singly Linked List

Doubly Linked List

Circular Doubly Linked List

Detect infinite loops

To find an infinite loop in a linked list move two pointers at different speeds through the list, if they are ever equal then there is a loop. The reason this works is because the faster pointer will eventually lap the slower pointer.

  1. Loop: every iteration compare pointer A and pointer B if they are equal then it is an infite loop.
  2. Pointer A: Move forward one element
  3. Pointer B: Move forward two elements
pointerA = pointerA.next;
pointerB = pointerB.next.next;
if(pointerA == pointerB) return true;
if(pointerB == null) return false;

See links at the bottom or top of this post for full code

  1. PointerA ="a" PointerB="b"
  2. PointerA ="b" PointerB="d"
  3. PointerA ="c" PointerB="c"
collapse
Add an element
  1. New element: Reference the next element
  2. Previous element: Reference the new element
x.next = b.next;
b.next = x;

See links at the bottom or top of this post for full code

collapse
Remove an element
  1. Current element: Reference null
  2. Previous element: Reference the next element
a.next = b.next;
b.next = null;

See links at the bottom or top of this post for full code

collapse
Reverse a Linked List
  1. Traverse the linked list
  2. At each node set its pointer to the previous node
currentNode.Next = previousNode;

See links at the bottom or top of this post for full code

collapse

Check out these links for more info:

My Linked List Code