Manish Virgat's Blog
Unraveling the magic of Linked Lists

Photo by Karine Avetisyan on Unsplash

Unraveling the magic of Linked Lists

Manish Virgat's photo
Manish Virgat
·

10 min read

Ever felt like you're lost in a maze of data structures? Fear not, intrepid explorer! Today, we're venturing into the exciting world of linked lists, a data structure as versatile as it is fun.

Imagine a train with interconnected carriages, each holding a piece of information. That's essentially what a linked list is like! Each carriage called a node, stores data and has a ticket directing it to the next carriage, forming a chain of information.

In the realm of data structures, linked lists stand tall as versatile and fundamental. They form the backbone of many applications, offering a dynamic structure that opens doors to efficient manipulation and storage of data.

Linked lists are data structures used to store a collection of elements. They consist of a sequence of elements, called nodes, where each node holds a piece of data and a reference to the next node in the sequence. The last node typically points to null, indicating the end of the list. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic memory management.

Section 1: Understanding Linked Lists

Definition and Basic Structure

A linked list is a linear collection of elements, called nodes, where each node contains both the data and a reference, or pointer, to the next node in the sequence. The basic structure of a node in a singly linked list typically consists of two parts:

  1. Data: This holds the value or information that the node is storing. It can be any type of data, such as an integer, a string, an object, etc.

  2. Pointer/Reference: This is a reference or address pointing to the next node in the sequence. In a singly linked list, each node points to the following node, and the last node typically points to null to indicate the end of the list.

Here is the structure of a Linked List in C:

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

Types of Linked Lists

  1. Singly Linked List: In this type, each node points only to the next node in the sequence. Traversal in a singly linked list starts from the head (the first node) and moves through subsequent nodes until the end is reached.

    Singly Linked Lists

  2. Doubly Linked List: In a doubly linked list, each node contains references to both the next and the previous nodes. This allows for traversal in both directions—forward and backward—which can be beneficial in certain operations but requires more memory to store the extra pointers.

    Doubly Linked List

  3. Circular Linked List: In a circular linked list, the last node points back to the first node, creating a circular structure. This can simplify certain operations, as it allows continuous traversal without reaching the end, but requires special handling to avoid infinite loops.

    Circular Linked List

Section 2: Advantages and Disadvantages:

Advantages:

  1. Dynamic Size: Linked lists can easily grow or shrink in size as elements are added or removed, without requiring pre-allocation of memory.

  2. Insertions and Deletions: Inserting or deleting elements in a linked list is efficient, especially if the position is known, as it involves changing pointers to adjust connections.

  3. No Wasted Memory: Linked lists utilize memory more efficiently compared to arrays, as they only use memory necessary for storing data and pointers.

Disadvantages:

  1. Random Access: Unlike arrays, linked lists do not support direct access to elements by index. Traversal from the head (or sometimes the tail) is necessary to reach a specific node.

  2. Memory Overhead: Each node in a linked list requires additional memory for storing pointers, which can lead to higher memory overhead compared to arrays.

Section 3: Operations

Insertion

  1. Insertion at the Beginning:

    • Efficient and straightforward.

    • Create a new node, set its data, and point it to the current head.

    • Update the head to point to the newly inserted node.

        void insertAtBeginning(Node*& head, int val) {
      // Create a new node with the given value
      Node* newNode = new Node(val);
      // Set the new node's next to the current head
      newNode->next = head;
      // Update the head to point to the new node
      head = newNode;
  }

  2. Insertion at the End:

    • Traverse the list until reaching the last node.

    • Create a new node, assign its data, and set it as the next node of the current last node.

    • Update the new node as the new last node.

        void insertAtEnd(Node*& head, int val) {
      // Create a new node with the given value
      Node* newNode = new Node(val);

      // If the list is empty, make the new node the head
      if (head == nullptr) {
          head = newNode;
          return;
      }

      // Traverse to the last node
      Node* temp = head;
      while (temp->next != nullptr) {
          temp = temp->next;
      }

      // Link the new node to the end of the list
      temp->next = newNode;
  }

  3. Insertion at a given position:

    • Locate the desired position using traversal.

    • Create a new node and adjust pointers to include it in the sequence.

        void insertAtPosition(Node*& head, int val, int position) {
      // Create a new node with the given value
      Node* newNode = new Node(val);
      // If position is 0, insert at the beginning
      if (position == 0) {
          newNode->next = head;
          head = newNode;
          return;
      }

      // Traverse to the node at position - 1
      Node* temp = head;
      for (int i = 0; temp != nullptr && i < position - 1; ++i) {
          temp = temp->next;
      }

      // If position is out of range, do not insert
      if (temp == nullptr) {
          printf("Position out of range.\n");
          return;
      }

      // Insert the new node at the given position
      newNode->next = temp->next;
      temp->next = newNode;
  }

Deletion

  1. Deletion at the Beginning:

    • Update the head to point to the next node of the current head.

    • Delete the previous head node.

        void deleteAtBeginning(struct Node** head) {
      // Check if the list is empty
      if (*head == NULL) {
          printf("List is empty. Nothing to delete.\n");
          return;
      }

      // Create a temporary node to store the head
      struct Node* temp = *head;

      // Move the head pointer to the next node
      *head = (*head)->next;

      // Free the memory of the node that was at the beginning
      free(temp);
  }

  2. Deletion at the End:

    • Traverse the list to reach the second-to-last node.

    • Update its reference to null, designating the current last node for deletion.

        void deleteAtEnd(struct Node** head) {
      // Check if the list is empty
      if (*head == NULL) {
          printf("List is empty. Nothing to delete.\n");
          return;
      }

      // Check if there is only one node in the list
      if ((*head)->next == NULL) {
          // Free the memory occupied by the single node
          free(*head);
          *head = NULL; // Set head to NULL since the list is now empty
          return;
      }

      // Create a temporary node to traverse the list
      struct Node* temp = *head;

      // Traverse the list until the second-to-last node
      while (temp->next->next != NULL) {
          temp = temp->next;
      }

      // Free the memory of the last node
      free(temp->next);

      // Set the next of the second-to-last node to NULL,
      // effectively removing the last node from the list
      temp->next = NULL;
  }

  3. Deletion at Value or Position:

  • Search for the node with the specified value or position.

  • Adjust pointers to skip over the node to be deleted and free its memory.

      void deleteByValue(struct Node** head, int value) {
      // Initialize two pointers, current and prev
      struct Node* current = *head;
      struct Node* prev = NULL;

      // If the node to be deleted is the first node
      if (current != NULL && current->data == value) {
          *head = current->next; // Update head to the next node
          free(current); // Free the memory of the node to be deleted
          return;
      }

      // Traverse the list to find the node with the given value
      while (current != NULL && current->data != value) {
          prev = current;
          current = current->next;
      }

      // If the value is not found in the list
      if (current == NULL) {
          printf("Value not found in the list.\n");
          return;
      }

      // Update the pointers to skip the node to be deleted
      prev->next = current->next;
      free(current); // Free the memory of the node to be deleted
  }

      void deleteByPosition(struct Node** head, int position) {
      // Check if the list is empty
      if (*head == NULL) {
          printf("List is empty. Nothing to delete.\n");
          return;
      }

      struct Node* temp = *head;

      // If position is 0, delete the first node
      if (position == 0) {
          *head = temp->next; // Update head to the next node
          free(temp); // Free the memory of the node to be deleted
          return;
      }

      // Traverse the list to find the node at the given position
      for (int i = 0; temp != NULL && i < position - 1; ++i) {
          temp = temp->next;
      }

      // If position is out of range (temp is NULL or next is NULL),
      // or if position is the last node
      if (temp == NULL || temp->next == NULL) {
          printf("Position out of range.\n");
          return;
      }

      // Store the next of the node to be deleted
      struct Node* next = temp->next->next;

      // Free the memory of the node at the given position
      free(temp->next);

      // Update pointers to skip the deleted node
      temp->next = next;
  }

Time Complexity Analysis

  • Insertion:

    • Beginning: O(1)

    • End: O(n) in single-linked lists, O(1) with a reference to the tail

    • At given Position: O(n)

  • Deletion:

    • Beginning: O(1)

    • End: O(n)

    • By given Position or value: O(n)

Section 4: Practical Applications

  1. Dynamic Memory Allocation: Linked lists facilitate dynamic memory allocation, allowing efficient use of memory resources. They're useful in scenarios where memory needs are unpredictable or where contiguous memory allocation isn't feasible, like in heap memory management.

  2. Implementation of Data Structures:

    • Stacks and Queues: Linked lists power the implementation of stacks (LIFO - Last In, First Out) and queues (FIFO - First In, First Out).

    • Hash Tables: Linked lists are used in hash tables to handle collisions. Each bucket in the hash table can be a linked list to store multiple elements hashing to the same location.

    • Graphs: Adjacency lists, used to represent graphs, are often implemented using linked lists.

  3. File Systems: File systems often use linked lists to maintain directories and manage file allocation tables (FAT). The file allocation table is typically a linked list structure that tracks available and used disk space.

  4. Undo Functionality in Text Editors: Implementing undo functionality in text editors involves keeping a linked list of changes made to the document. Each change is stored as a node in the linked list, enabling easy traversal and reversal of changes.

  5. Polynomials in Mathematics: In algebraic manipulations, linked lists can represent polynomials efficiently. Each node represents a term in the polynomial, containing coefficient and exponent values.

  6. Music and Media Players: Linked lists can be used to create playlists in music or media players. Each node contains information about a song or media file, linked together to create a playlist structure.

  7. Garbage Collection: In some garbage collection algorithms, linked lists are used to track memory allocations and deallocations, facilitating efficient memory cleanup.

  8. Networking: Linked lists can be used in various networking algorithms and data structures, such as managing routing tables or handling network packet queues.

Section 5: Further Reading

For Beginners:

For Intermediate Learners:

Interactive Learning:

For Practice:

Bonus:

And there you have it - the twists, turns, and pointers of the marvelous world of linked lists! Remember, just like the nodes in a linked list, connections in life are key. Whether it's linking nodes or linking ideas, these structures teach us the beauty of interconnection. So, the next time you’re sifting through code or strolling through life, embrace the linked list mindset - stay connected, stay curious, and keep the pointers of possibility always in mind! Now, go forth and code on, linkers of the world! With dedication and curiosity, you'll become a master of linked lists in no time!

Please leave your valuable feedback and connect with me on 𝕏, Linkedin.

#linkedlistsComputer Sciencedata structureslinked list, singly linked listlinked list