Linked List Data Structure

  • Linked list is one of the primary data arrangement along with arrays. Most other data structures are either implemented using Linked Lists or Arrays. For practical purposes, most Abstract Data Structures are implemented using Linked Lists in many programming languages.

    Linked list is a slightly different kind of linear data structure compared to arrays, queues or stacks. This is like a chain of nodes, with each node having 2 parts in its basic form. One part of the node to store the data and another part to store the reference to the next node memory location. So the nodes need not be placed in continuous memory location.

    Linked List Data Structure

    This type of structure allows efficient insertion and removal of nodes from any position just by updating the pointer values of 2 nodes. Linked List data structure has performance disadvantage for search and traversal operations.

    We know that sorted arrays helps in implementing algorithms of Logarithmic Complexity for search and traversals like binary search. For Linked Lists, there is no point in keeping the data sorted as elements are spread across different places in memory. That means, most of the Divide and Conquer Algorithms cannot be implemented in the same way as that of the array data structure.

    That being said, in real-world scenarios Linked Lists are of more use than that of Arrays, simply because of its mutable nature. Most Abstract Data Types like Lists, Stacks and Queues are implemented using Linked Lists in almost all Programming Languages.

    In general go for dynamic arrays for better search performance. For other cases use Linked Lists.

    Linked List Memory Allocation

  • Linked Lists vs Arrays

    Arrays and Linked Lists differ in how data is arranged in memory. That means, even though both are used to stored data, use cases of both structures are entirely different. Let us do a quick comparison.

    Arrays Linked Lists
    Arrays are stored in continuous memory space. Linked lists are not stored continuously.
    Arrays cannot be extended. Linked lists can be extended.
    Requires lesser space. More space needed than arrays.
    Search and traversal performance is better. Insert, update, delete operations are faster than arrays.
    Arrays have more chance of stack-overflow exception. Comparatively linked lists have lesser chance, because it can proceed till space for at-least a single node is available.

  • Types of Linked Lists

    Linked Lists can be classified into different types based on the number of address locations or how each nodes are connected.

    1. Singly Linked List

      This is the most basic type of linked list. Each node will have a space allocated for data and also for a pointer to the next node. Singly linked lists perform better on insert and delete operations. Singly linked lists allow traversal in one direction only.

      This forms the basis of ADTs like stacks, queues, lists in its basic form.

    2. Doubly Linked List

      Each node contains a space to store data and two different spaces to store 2 references, one to the next node and the other to the previous node.

      Doubly Linked Lists allow traversals in both directions making it more flexible. Using this type of data structure, we can design non-sequential search and traversal algorithms, for better search performance. Doubly Linked Lists occupy more memory space.

    3. Multiply Linked List

      Each node contains more than one links (pointer locations). That means, we can arrange the same data in different order. For example, keep a set of references to navigate the data in sorted order, another set to arrange the data based on the insertion time.

      This type of structures helps in including many features specific to arrays like faster search, at the expense of more memory.

    4. Circular Linked List

      Any types of the above mentioned linked list can be mage circular by storing the address of the first node in the last node reference location. Useful in algorithms that needs to access an entire list continuously and repeatedly till a base case is reached.

  • Linked Lists Uses

    Most of the high level programming languages follow Linked List data structure to implement collections like ArrayList, List, Stack, Queue, etc.

    Many of the latest operating systems uses doubly linked lists to maintain references to active processes and threads, singly linked lists to perform arithmetic operations, etc.

    Linked Lists can be used to store adjacent vertices of a graph in adjacency list representation.

    Linked Lists concept can be seen in back and next buttons of web browsers, navigating to next and previous items in a video player, etc.

Absolute Code Works - Python Topics