Menu Close

Linked List Introduction

Linked List:

  • It is a linear data structure.
  • In linear data structure one element is connected to only one element.

Differentiate Arrays from Linked Lists?

  • Array is linear.
  • Array elements get consecutive locations.
  • We access array elements easily using index.
  • Insertions and Deletions taking time – Shifting of elements after insertion and Deletion takes much time.
  • Linked List stores information in the form of nodes.
  • Nodes get memory in random locations and connected using links(pointers)
  • Insertions and Deletions are faster compare to Array (Array List)
  • Inserting and deleting nodes depends on connections.
  • In My application, we insert the records only once and process (access) every time. Array List is recommended.
  • We use linked lists when our application requires continuous insertions and deletions of records.

We have Different types of Linked Lists:

  1. Singly linked list
  2. Doubly linked list
  3. Circular linked list

Singly Linked List:

  • Every Node has 2 Fields
    • Data field
    • Link field
  • Link Filed is pointer type
  • Data means int, float, structure…….
  • Last node link is NULL – No other record to connect.

Node representation:

  • We represent the node with structure type as follows.
  • Structure is used to represent different data types set.
  • Node has 2 fields representing data and link of different types as follows.

To store Emp data into Linked List node, then Node as follows:

  • In the above diagram, we take data as int type.
  • We can store records information like Employee details, Student details, Account details…
  • We can represent the data field as multiple fields to store records information.
  • The following diagram represents a node that stores Employee details and link to next node.

Doubly linked List:

  • Doubly linked list is also called Bi-directional linked list.
  • We can process the information either in forward direction as well as in backward direction.
  • Every node has 2 pointers pointing to next node and previous node.
  • Every node contains 3 fields.
    • Data filed
    • Link to previous node
    • Link to next node

List representation:

  • First Node left link is NULL
  • Last Node right link is NULL

Circular Linked List:

  • Every node as data filed and link filed in Singly circular linked list
  • Last node link is connected to first node.

Node representation:

  • We can implement circular linked list in 2 ways.
    • Using singly linked list
    • Using doubly linked list
  • The following diagram represents circular singly linked list in which the last node link is pointing to root node in the list.

Circular double linked list:

  • In Circular doubly linked list:
    • Last node connects to first node
    • First node is connected to last node.
  • The following diagrams shows how the structure will be