What is a linked-list?

  • It is a non-contiguous linear data structure where a sequence of nodes are connected to one another via a reference pointer.
  • Each node stores the data and address of the next node.

What does each node have?

  • A node in a linked-list typically have two components:
    1. Data: Holds the value/data of the associated node
    2. Next Pointer: Stores memory address (reference pointer) of the next node in the sequence
    3. Head and Tail: The head node will be the way to access the linked list–it points to the first node of the list. The tail node is the last node in the list. It will point to NULL (or nullptr) which will indicate the end of the list.

When a linked-list is necessary

  • When you need to implement a queue/stack by scratch.
  • When you need to insert/delete items from the middle of a list in constant time ( O(1) ). No shifting of elements after insertion or deletion is necessary–just need to update the address of the reference node.
  • When you know the size of the list ahead of time and memory efficiency is a thing to be considered.

What are some advantages of using a linked-list?

  1. Dynamic Size: Linked-list can grow or shrink dynamically; memory allocation is done at runtime.
  2. Insertion and Deletion: adding and removing elements from a linked list will take constant time, making them efficient on large lists.
  3. Flexibility: Linked-list can be easily reorganized and modified without requiring contiguous block of memory.

What are some disadvantages of using a linked-list?

  1. Random Access: Linked-list do not allow direct access to elements via index, so if you need to access a specific element, you must traverse through the list.
  2. Extra Memory: Linked-list require additional memory for storing pointers.

Node Class/Struct Layout

  • The node class/struct must have:
    1. data (of any data type)
    2. a “next” reference node

C++ Code Example:

struct Node {
  int data;
  struct Node* next;
};

Python Code Example:

class Node:
  def __init__( self, data ):
    self.data = data;
    self.next = None;

What are ways to traverse through a linked-list?

  1. Use an iterative approach ( while or for loop where the current node is not pointing to NULL/nullptr ).
  2. Recursive approach (same condition as the iterative approach).