Linked List In Data Structure And Algorithm (C++/Python/Java)

What is Linked List?

A linked list is a linear data structure that consists of a sequence of nodes, where each node stores a reference to an object and a reference to the next node in the sequence. The objects stored in the linked list are called elements.

Linked lists are useful for dynamic data structures because they can grow and shrink as needed. They can be used to implement lists, stacks, queues, and other data structures.

Types of Linked List

There are several types of linked lists, including:

Singly linked list

In a singly linked list, each node has a reference to the next node in the sequence, but not to the previous node. This means that you can only traverse a singly linked list in a single direction, from the head (first node) to the tail (last node).

Doubly linked list

In a doubly linked list, each node has a reference to both the next node and the previous node in the sequence. This means that you can traverse a doubly linked list in both directions.

Circular linked list

In a circular linked list, the last node in the sequence points back to the first node, creating a circular loop. This means that there is no clear head or tail of the list, and you can traverse the list in either direction

Singly linked lists are the most common type of linked list, and they are often used to implement stacks and queues. Doubly linked lists are less common, but they are useful for certain data structures that require bidirectional traversal, such as double-ended queues. Circular linked lists are rarely used because they are not as efficient as other types of linked lists for most data structures.

Applications

Here are some common applications for linked lists:

Dynamic data structures: Linked lists are useful for implementing dynamic data structures, such as stacks and queues, because they can grow and shrink as needed.
Associative data structures: Linked lists can be used to implement lists, maps, and other associative data structures.
Graphs and tree structures: Linked lists can be used to implement graphs and tree structures, such as linked lists of children in a tree node.
Ordered lists: Linked lists can be used to implement lists of items that are accessed in a specific order, such as a list of recently visited web pages.
Polynomial manipulation: Linked lists can be used to represent polynomials and perform operations on them, such as addition and multiplication.
Undo/redo operations: Linked lists can be used to implement undo/redo functionality in text editors and other applications.
Dynamic memory allocation: Linked lists can be used to manage dynamic memory allocation, by keeping track of allocated blocks of memory and freeing them when they are no longer needed.

Advantages Of Linked List

Here are some advantages of linked lists:

Resizable: Linked lists can be resized easily because you only need to change the pointers in the nodes to add or remove elements from the list.
Dynamic memory allocation: Linked lists can be implemented using dynamic memory allocation, which allows them to grow and shrink as needed.
Flexible size: Linked lists can be used to implement data structures that do not have a fixed size, such as stacks and queues.
Insertion and deletion: Linked lists have efficient insertion and deletion operations because you only need to change the pointers in the nodes to add or remove elements from the list.

Disadvantages Of Linked List

Here are some disadvantages of linked lists:

Memory overhead: Linked lists require more memory overhead than arrays because each node in a linked list requires an additional reference (pointer) to the next node.
Random access: Linked lists are not as efficient as arrays for random access, because you must follow the references from the head of the list to get to a specific element.
Cache-unfriendly: Linked lists are not as cache-friendly as arrays, because the elements in a linked list are not stored contiguously in memory.
Auxiliary data structure: Linked lists are often used as auxiliary data structures, meaning that they are used to implement other data structures such as stacks and queues. This can make them less efficient for certain operations compared to data structures that are optimized for those operations.

Linked List vs Array

Linked lists and arrays are both linear data structures that can be used to store and access data. However, they have several differences:

Size: Arrays have a fixed size, which means that you must specify the size of the array when you create it, and you cannot change the size of the array later. Linked lists, on the other hand, can grow and shrink as needed, because they are implemented using dynamic memory allocation.
Memory allocation: Arrays are stored in contiguous blocks of memory, whereas linked lists are stored as a series of nodes that are linked together using pointers. This means that linked lists require more memory overhead than arrays because each node in a linked list requires an additional reference (pointer) to the next node.
Access time: Arrays have constant-time access to elements because you can access any element in an array using its index. Linked lists, on the other hand, have linear access time to elements, because you must follow the references from the head of the list to get to a specific element.
Insertion and deletion: Inserting and deleting elements from an array can be slow, because you may need to shift the elements of the array to make room for the new element or fill the gap left by the deleted element. Linked lists, on the other hand, have efficient insertion and deletion operations, because you only need to change the pointers in the nodes to add or remove elements from the list.
Cache-friendliness: Arrays are generally more cache-friendly than linked lists because the elements in an array are stored contiguously in memory. This means that it is more likely that the elements of an array will be in the cache when you access them, which can improve performance.

Overall, arrays are generally more efficient for random access and cache-friendly access patterns, whereas linked lists are more efficient for inserting and deleting elements and for implementing dynamic data structures. The choice between using an array or a linked list depends on the specific requirements of your application.

Code

Code in C++:

Here is an example of a singly linked list in C++:

#include <iostream>

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

int main() {
  Node* head = nullptr;
  Node* tail = nullptr;

  // Append a new element to the list
  Node* new_node = new Node{5, nullptr};
  if (tail) {
    tail->next = new_node;
  } else {
    head = new_node;
  }
  tail = new_node;

  // Traverse the list
  Node* current = head;
  while (current) {
    std::cout << current->data << std::endl;
    current = current->next;
  }

  // Free the memory used by the list
  current = head;
  while (current) {
    Node* next = current->next;
    delete current;
    current = next;
  }

  return 0;
}

Code in Python:

Here is an example of a singly linked list in Python:

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node

    def __iter__(self):
        current = self.head
        while current:
            yield current
            current = current.next

Code in Java

Here is an example of a singly linked list in Java:

class Node {
  int data;
  Node next;

  public Node(int data) {
    this.data = data;
  }
}

class LinkedList {
  Node head;
  Node tail;

  public void append(int data) {
    Node newNode = new Node(data);
    if (tail != null) {
      tail.next = newNode;
    } else {
      head = newNode;
    }
    tail = newNode;
  }

  public void printList() {
    Node current = head;
    while (current != null) {
      System.out.println(current.data);
      current = current.next;
    }
  }
}

public class Main {
  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    list.append(5);
    list.append(10);
    list.append(15);
    list.printList();
  }
}