DS Menu

Linked List Introduction



What is a Linked List?

A linked list is a data structure used to organize a sequence of elements, where each element contains a reference (or link) to the next element in the sequence. Unlike arrays, linked lists are not stored in contiguous memory locations, which makes them dynamic and easily expandable.

A simple form of a linked list, known as a singly linked list, includes nodes that have two fields:

  • A "data" field to store the actual value.
  • A "address" field, which is a reference to the next node in the list.

A doubly linked list includes two references in each node: one to the next node and another to the preceding node.

 
 

linked list ADTs

1) Creation
2) Insertion at the beginning
3) Insertion at the end
4) Insertion at the position
5) Deletion from the beginning
6) Deletion from the end
7) Deletion at the position
8) Traversal
9) Searching


Advantages of linked list over arrays

Linked lists and arrays are both fundamental data structures, but they have distinct advantages and disadvantages. Here are some advantages of linked lists over arrays:

1. Dynamic Size:

  • Linked List: The size of a linked list is dynamic, meaning you can allocate and deallocate memory on-the-fly, and it can grow or shrink as required.
  • Array: An array is a static data structure, meaning its size is fixed at the time of creation. Dynamic arrays exist but require resizing and data copying to expand.

2. Ease of Insertions and Deletions:

  • Linked List: Inserting or deleting an element at any position is an O(1)O(1) operation, provided we have a pointer to the node before the one we wish to delete.
  • Array: Inserting or deleting elements requires shifting the elements, making it an O(n)O(n) operation in the worst case.

3. No Wasted Memory:

  • Linked List: Each node is allocated only when needed, avoiding wasted memory.
  • Array: You might allocate more memory than needed to avoid frequent resizing, leading to wasted space.

4. Better Cache Locality for Non-Sequential Access:

  • Linked List: If you're inserting or deleting elements often, linked lists maintain better cache locality for those specific operations, as fewer elements need to be moved around.
  • Array: Insertion or deletion at arbitrary points requires data shifting, resulting in poorer cache locality for these types of operations.

5. Flexibility:

  • Linked List: Variations like doubly-linked lists and circular linked lists offer more flexibility for specific use-cases.
  • Array: Arrays are more rigid in their structure and don't offer such built-in variations.

6. Simplicity of Memory Allocation:

  • Linked List: Memory is allocated for each new element during runtime, typically from the heap, which is a straightforward operation.
  • Array: Dynamic arrays require resizing, which involves allocating new memory and copying old elements, a more complex process than in linked lists.

7. Complexity of Element Update:

  • Linked List: When an element needs to be added or removed, only the references in the adjacent nodes need to be updated.
  • Array: Depending on the operation, shifting elements may be required, which can be computationally expensive.

Limitations of Linked List:

  • Random Access: One major drawback is that linked lists do not provide constant-time access to individual elements. To access an element, you have to start at the head and follow the references until you get to the desired element.
  • Extra Memory: Each node in a linked list needs to store at least one reference to another node, requiring extra memory overhead.
  • Cache Locality: Poor cache locality can sometimes make linked lists perform poorly compared to arrays for certain types of tasks.
Next Topic :Single Linked List