Linked List Data Structure (Introduction)

June 16, 2023

linked lists

What are Linked List in Data Structure?

A linked list is a linear data structure. In which we can sequentially store the data. Unlike an array linked list is a dynamic data structure the size of a linked list can grow or shrink depending on the situation.

However, in the case of Arrays, we need to predefine the size and we can’t add more items than the max size defined.

More Information

The element of a linked list is called a node. Every element or node contains two main entities first entity is the information or the data whereas the second entity is the pointer to the next node.

The structure of the linked list is like a train. A linked list has the following components –

  • Data: Data is the value stored in it, it could be anything an integer or a string or anything else really.
  • Pointer (Link) – Each linked list contains a pointer which points to address of the next node in the linked list train.

Apart from this the following are also keywords used in linked lists –

  • Node – Any single unit of a linked list, its data and pointer(s), is called a node.
  • Head: First is the head who is defined the beginning of the list.
  • Tail: second is tail which defined end of the list.
Linked List Introduction

Why we use Linked List in Data Structure?

Generally for storage arrays are used. But, there are many many disadvantaged with arrays –

1. Fixed Size

  • The size of the array is fixed and needs to be pre-defined
    • Example – int a[10]; or int a[ ] = {1, 2, 3, 4, 5}
    • We can’t declare an array without declaring the size.

2. Memory wastage (Not Optimised)

  • If you declare an array of size 10 and just assign values to first two elements
  • The memory is allocated to all of them even though, we may not end up using them.

3. Need for Contiguous Memory

  • Arrays need Contiguous memory, which some times is bad.
    • Example – Consider there are only three memories of size 10, 10 and 400
    • We need to store an array of size 15
    • In this case, the array will use memory location is size 400 and not combine memory A and B of size 10 and 10 respectively.
    • Thus wasting a lot of memory

4. Inserting in Array is expensive

  • Let us say you have an array a[] = {10, 20, 40, 60, 80} and we need to add 50 in the same sorted format.
  • Then, we have to move all elements after 40 to one additional position
  • Also, the same goes for deletion if we want to delete 20. Then all elements after it have to be moved to one position in the opposite direction.

Linked List in Data Structure

Advantages

  • Ease of insertion and deletion.
  • Dynamic Size

Disadvantages

  • We have to search elements linearly, and can’t do random access
  • We can’t do efficient searches like binary search
  • Extra space for pointers is needed
  • Linked lists are not cache friendly as arrays are stored in contigious format they can be cached easily
  • Loss of data threat is there, if we lose one pointer location the rest of linked list can’t be accessed.
DSA desktop gif
DSA mobile gif

Insertion in Circular Linked List

Deletion in Circular Linked List

Split a Circular Linked List in two halves

Sorted Insert In Circular Linked List

Count nodes in Circular Linked List

Types of Linked link

There are three types of linked list, that are mentioned in following ways-

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

Singly-linked list

In a singly list there is the two field on the list.

  • Data: First field is data that it stores
  • Link (pointer): Link that refers to address of the next linked list node.
  • The last node of linked lits points to NULL and means the end of the list

In a Singly linked list node, it only contains the address of the next node and not the previous node, so we can only traverse in one direction only.

Structure of Singly Linked List

struct Node {
   int data;
   struct Node* next;
};
class Node {
  public:
    int data;
    Node* next;
};
class LinkedList {
  Node head; // head
  
  // Linked list Node
  class Node {
    int data;
    Node next;

    // constructor to initialize
    Node(int d) { 
      data = d; 
    }
  }
}
# Node class
class Node:
    # Function to initialize the node object
   def __init__(self, data):
   self.data = data # Assign data
   self.next = None # Initialize
   # next as null

# Linked List class
class LinkedList:

   # Function to initialize the Linked
   # List object
   def __init__(self):
       self.head = None

Doubly linked list

A doubly linked list is a kind of complex linked list, in which it contains the address of the previous node as well as the next node. A doubly linked list contains the following –

  • Data: The data present in the node.
  • Link (Previous) – A pointer to the previous node in the linked list.
  • Link (Next) – A pointer to the next node in the linked list

In this way, for a doubly-linked list we can travel in both directions for traversals.

Doubly Linked List

Structure of Doubly Linked List

struct Node {
   int data;
   struct Node* next, prev;
};
class Node {
  public:
    int data;
    Node* next, prev;
};
class LinkedList {
  Node head; // head
  
  // Linked list Node
  class Node {
    int data;
    Node next, prev;

    // constructor to initialize
    Node(int d) { 
      data = d; 
    }
  }
}
# Node class
class Node:
    # Function to initialize the node object
   def __init__(self, data):
   self.data = data # Assign data
   self.next = None # Initialize    # next as null
   self.prev = None # Initialize    # prev as null

# Linked List class
class LinkedList:

   # Function to initialize the Linked
   # List object
   def __init__(self):
       self.head = None
Introduction to Doubly Linked Lists

Circular linked list

  • This is a type of linked list in which the last node points to the starting node.
  • There is no null at the end.
  • A circular linked list can be a singly circular linked list and doubly circular linked list.
  •  In Circular linked list there exist no nodes which have null at address space.
Linked List CC 
struct Node {
   int data;
   struct Node* next;
};
//last node will have the address of the head 
class Node {
  public:
    int data;
    Node* next;
};
//last node will have the address of the head 
class LinkedList {
  Node head; // head
  
  // Linked list Node
  class Node {
    int data;
    Node next;

    // constructor to initialize
    Node(int d) { 
      data = d; 
    }
  }
}
//last node will have the address of the head 
# Node class
class Node:
    # Function to initialize the node object
   def __init__(self, data):
   self.data = data # Assign data
   self.next = None # Initialize    # next as null

# Linked List class
class LinkedList:

   # Function to initialize the Linked
   # List object
   def __init__(self):
       self.head = None
//last node will have the address of the head
Introduction to Circular Linked Lists

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Linked Lists

Linked List is one of the most crucial topics which is easy once understood thoroughly. This topic is very important for both your college semester examinations as well as for placement purposes.

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++ | Java
    • Insertion at nth position in singly Linked List  – C | C++ | Java
    • Insertion at end in singly Linked List  – C | C++ | Java
  • Deletion in singly Linked List  – C | C++ | Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++ | Java
  • Linked List Insertion and Deletion – C | C++ | Java
  • Reverse a linked list by changing links between nodes – C | C++ | Java
  • Linked List insertion in the middle – C | C++ | Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++ | Java
  • Insertion in a Sorted Linked List – C | C++ | Java
  • Delete alternate nodes of a Linked List – C | C++ | Java
  • Find middle of the linked list – C | C++ | Java
  • Reverse a linked list in groups of given size – C | C++ | Java
  • Find kth node from end of the linked list – C | C++ | Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++ | Java
  • Check whether linked list is palindrome or not – C | C++ | Java
  • Fold a Linked List – C | C++ | Java
  • Insert at a given position – C | C++ | Java
  • Delete at a given position – C | C++ | Java

Doubly Linked List

Circular Linked List

Operating System Process Synchornization

Linked Lists

Linked List is one of the most crucial topics which is easy once understood thoroughly. This topic is very important for both your college semester examinations as well as for placement purposes.

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++ | Java
  • Insertion at nth position in singly Linked List  –
    C | C++ | Java
  • Insertion at end in singly Linked List  –
    C | C++ | Java
  • Deletion in singly Linked List  –
    C | C++ | Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++ | Java
  • Reverse a linked list by changing links between nodes –
    C | C++ | Java
  • Print reverse of a linked list without actually reversing –
    C |C++ | Java
  • Print reverse of a linked list without actually reversing –
    C |C++ | Java
  • Insertion in the middle Singly Linked List –
    C | C++ | Java
  • Insertion in a Sorted Linked List –
    C | C++ | Java
  • Delete alternate nodes of a Linked List –
    C | C++ | Java
  • Find middle of the linked list –
    C | C++ | Java
  • Reverse a linked list in groups of given size –
    C | C++ | Java
  • Find kth node from end of the linked list –
    C | C++ | Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++ | Java
  • Check whether linked list is palindrome or not –
    C | C++ | Java
  • Fold a Linked List –
    C | C++ | Java
  • Insert at given Position –
    C | C++ | Java
  • Deletion at given Position –
    C | C++ | Java

Doubly Linked List

  • Introduction to Doubly Linked list in Data Structure
    Click Here
  • Doubly Linked List in –
    C | C++ | Java
  • Insertion in doubly linked list –
    C | C++ | Java
  • Insertion at beginning in doubly linked list –
    C | C++ | Java
  • Insertion at end in doubly linked list –
    C | C++ | Java
  • Insertion at nth node in doubly linked list –
    C | C++ | Java
  • Deletion in doubly linked list  –
    C | C++ | Java
  • Deletion from beginning in doubly linked list :
  • Deletion from nth in doubly linked list :
    C | C++ | Java
  • Deletion from end in doubly linked list :
    C | C++ | Java
  • Insertion and Deletion in a  doubly linked list :
    C | C++ | Java
  • Insertion in the middle in a  doubly linked list :
    C | C++ | Java

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • Insertion in Circular Linked List –
    C | C++ | Java
  • Insertion at the beginning–
    C | C++ | Java
  • Insertion at the end –
    C | C++ | Java
  • Insertion at nth position –
    C | C++ | Java
  • Deletion in Circular Linked List –
    C | C++ | Java
  • Deletion from beginning in Circular Linked List –
    C | C++ | Java
  • Deletion from nth position in Circular Linked List –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

6 comments on “Linked List Data Structure (Introduction)”


    • Care

      You cannot implement Linked List in Python, as Python doesn’t have the concept of Pointers. But in Python you can use List, or other data structures like Dictionaries which may help you in storing the data efficiently

      5

    • chellabangarkrishna

      You can implement in Python as Well !
      here is the sample Code!

      class Node:
      def __init__(self, value):
      self.value = value
      self.next = None
      class LinkedList:
      def __init__(self):
      self.head = self.tail = None
      def insert(self, value, location):
      newNode = Node(value)
      if self.head is None:
      self.head = self.tail = newNode
      else:
      #Begining loc = 0
      if location == 0:
      newNode.next = self.head
      self.head = newNode
      elif location == 1:
      self.tail.next = newNode
      self.tail = newNode
      else:
      curNode = self.head
      index = 1
      while index < location:
      curNode = curNode.next
      index += 1
      newNode.next = curNode.next
      curNode.next = newNode

      0