What is Linked List in DSA?

Share

Before getting started with a linked list, it is important to know the concept of a list.
A list is a sequential data structure, ie. a collection of items accessible one after another beginning at the head and ending at the tail. In other words, a list is a mutable structure that stores either primitive values ( int, char, etc) or objects. There are two common implementation methods of lists. They are:

  1. Static implementation of list:
    Static implementation stores the elements of list in contagious memory location. The position of each elements in the list are given by an index from 0 to n-1, where n is the number of elements in the list. In this implementation, memory allocation for the list should be done at the creation time , i.e the size of the list should be known in advance.

    There are certain problems with static implementation of lists :

    # Insertion and deletion are time consuming and memory consuming.
    The insertion and deletion of an element to and from the last index of the list is not problamatic, but insertion and deletion at the specified index is very expensive. for example, inserting at postion 0 ( i.e a new first element) requires first pushing the entire array elements one step right to make room for the new element, whereas deleting element from first index requires shifting entire array elements one step left to cover up the empty space created by deletion.
  2. Dynamic implementation of list (Linked List):
    This implementation allocates the elements of list dynamically (and elements allocated dynamically does not demand contagious memory location). So in dynamic allocation it is not necessary to know the size of the list in advance. The list elements are not stored in contagious memory location though they belong to the same list , they are linked to each other by address of next elements.

    So, linked list is a linear data structure in which list elements are dynamically allocated and in which elements point to each other to define a linear relationship. The elements of linked lists are called nodes.

    Each nodes has minimum 2 fields : Data field (also called info field) and pointer field.

    * Data field stores user provided input values.
    * Pointer field stores the address of its successor node.

    The first node in the linked list is pointerd by head pointer which contains the address of the first node.

Commonly, there are four types of linked lists. They are:

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List
  4. Doubly Circular Linked List

Check: Creating a basic linked list in the C program.

Share

Leave a Reply

Your email address will not be published.

%d bloggers like this: