Linked List



A Singly Linked List


Definition: A collection of elements stored together in a linked, linear format where each piece of data contains a reference to the next piece of data in the list (or in the case of a doubly linked list, next and previous). Linked Lists are not indexed like arrays. There are 3 main types of Linked Lists:

  1. Singly Linked List: Each piece of data is linked to the piece of data in front of it.


  2. Doubly Linked List: Each piece of data is linked to the piece of data in front of it AND behind it.


  3. Circularly Linked List: A singly Linked List but where the last element of the list is linked back to the first element to create a cycle.



Real Life Example: A conga line! Everyone in the line is connected to the person in front of them with their hands. When someone joins or leaves the line, people affected by the change must reconnect their hands so that the line stays intact.




Note: The first node in a linked list (the one farthest to the left with no other nodes pointing to it) is called the head. The last node is a linked list (the one farthest to the right that points to null) is called the tail.




Basic Singly Linked List Operations:

  1. Adding an element. By default, adding an element to a singly linked list places it at the end of the list, making it the new tail. The previous tail is then reconnected to point towards the newly added tail. If you would like to add the node at another location, see operation #2. See the fun fact #2 at the bottom for an explanation about the "null" reference following the tail.
  2. Inserting an element. The node to the left of the insertion spot is reconnected to the inserted note and the node to the right of the insertion spot is now pointed to by the inserted node.
  3. Removing an element. The element to the left of the removal spot is reconnected to the element to the right of the removal spot.
  4. Changing an element. The element is simply changed in place, commonly referred to as "setting".



Fun Fact #1: Unlike in a graph, a node in a Linked List consists of the data AND the arrow(s) stemming from it (but not the ones pointing towards it).


Fun Fact #2: In a singly linked list, the tail node points towards "null" (meaning empty) to signify the end of the Linked List. This is necessary because searching a Linked List is done by following the "arrows" node by node (much slower than in an array) and without "null", there is no instruction for the search to stop once it reaches the final node. The same goes for doubly linked lists except a "null" value is pointed to by the tail AND the head.



Commonly Used In:



Other Similar Data Structures: