Introduction

  • A list is dynamic in nature and can have varying size.
    Which is the first and foremost different between a linked list and other data types as QUEUEs and STACKs etc.
  • Linked list is a Non primitive Linear Data Structure
  • When linked lists are implemented using dynamic allocation:
    1. Efficient Memory Ultilisation
    2. Insertion and deletion operations are easier and efficient
    3. We can perform complex manipulation without any prior idea of memory space available.
      For example: We do not get the overflow condition that we get in STACKs and QUEUEs.
    4. Arbitrary memory locations.
      Though they might or might not be stored in consecutive memory location , it does not matter as
      Linked lists relies on the logical connection and not the physical.
      It specified its link to the address of the other [ or the next ] node in its own node itself called a link or a pointer.


    5. Disadvantage


      Since it stores both the data and the link pointers in the memory , It has a space / memory overhead.
      Which is the Only disadvantage of Linked-Lists.



    • Components of a linked list

    A singly linked list (or) one-way list isa linear collection of data elements called nodes, where each node is divided into two parts:
  • Informatoin Field
  • Pointer to the next node/link field

    • Some memes

    meme 1
    meme 2
    meme 3
    meme 4
    meme 5
    meme 6
    meme 7
    meme 8
    meme 9
    meme 10



    From the holy pages above , you might have understoood that the linkedlist if ending [ non - circular ] ends with null in the last node's link field that is '\0'

    Null Pointer: the last pointer , i.e the last node stores the value '\0' indicating NULL and termination of the list
    External Pointer: This is the pointer to the first element of the list [ start ]

    Linked List in memory

    Static representation using array
  • Equal length for both the information and the link fields
  • Stored parallelly in 2 separate arrays
    • Dynamic representation using free pool of storage
  • Memory is allocated randomly , no contiguous memory is allocated
  • You don't have to specify the exact space of the list , since it allocates memory in the run time
  • code: 
            
        struct node 
        {
        int info;
        struct node * link;
        };
    Here each element takes up enough space that is described by its data type [ not the same way in union ].
  • The link variable here is called as a self - referential pointer which stores to location to a data structure of the same type



    • Types of Linked Lists

    1. Singly Linked List
    2. Circular Linked List
    3. Doubly Linked List
    4. Header Linked List
    5. Circular Doubly Linked List
    Singly Linked List one-way list
    It just a normal list , which has info and link field where link acts as a pointer , with a header and last node.
    single linked list representation
    Circular Linked List
    Same as singly linked list , except for the starter node, instead a last is maintained which points to the start node.
      Advantages
    1. The circular list can be traversed to any node from any node
    2. All the nodes link address will have valid address, instead of NULL pointer
    3. A node can be inserted at or deleted from any position of the linked list
    4. One can start at any node in thelist and traverse the whole list
    circular singly linked list representation
    Doubly Linked List
    You can traverse both ways
      Advantages
    1. If any particular node is known , we can get both the successor and predessor
      That makes Deletion and Insertion easy and efficient
    2. The doubly linked list is used to represent the trees effectively
      Disadvantage
    1. Extra memory is required to store the back pointer


    doubly singly linked list representation
    Header Linked List
    The header node contains special information such as number of nodes in the list.
    Largest element of the list
    Smalled element of the list
    Sum of the elements of the list
    Address of the last node
    While counting the number of nodes, Header node will not ne considered .
    Start is always pointing to the header node/
    It may have flag that marks it as a header node.
    There are two main types
    1. Grounded Header Linked List
    2. Circular Header Linked List
    Grounded Header Linked List: Where the last node of the linked list points to NULL .
    Circular Header Linked List: The last node points to the header node is called circular header linked list .
    CirCular Doubly Linked List
    Similar to doubly linked list, The forward field of the last node points to the first node
    The backward field of the first node points to the last node .
      Advantages
    1. Any node can be accessible from any given node
    2. It can be traversed in forward and backward direction
    3. It is used to represent trees.
    4. this ismplifies list management effectively.
      5. Disadvantages
    5. Extra memory is required to store the back pointer
    Next