Introduction to Linked Lists

Linked List is a linear data structure whose elements are linked together by links. These links are connected in a sequence and each link carries its own data and the address to the next link thus forming a chain.

Diagram:

 

Linked List in Data Structure

 

 

As evident by the diagram above, the Linked list has:

  • A link element called first.
  • Each link has its own data item and the address to the next link.
  • The last link of the list is null

 

Applications of Linked Lists
  • Linked lists are used to implement stack, queue or graphs.
  • Linked Lists are used to insert elements at the beginning or the end of the list.
  • We don’t need to worry about the size of the list in the linked lists.

 

 

Advantages of Linked Lists
  • Insertion and deletion operations can be easily carried out.
  • It reduces access time.
  • Easily implements stacks and queues.

 

Disadvantages of Linked Lists
  • Pointers need extra memory for storage thus memory gets wasted.
  • Random access to the elements is not possible. The sequential approach has to be followed.
  • Reverse Traversing is difficult.

 

Types of Linked Lists

There are three major types of Linked Lists. Lets discuss each in detail.

Singly Linked List

Singly linked list as the name suggests contains the nodes with data and the next part. Next part contains the address to the next node in the sequence.

Diagram

 

Singly Linked List

 

Doubly Linked List

In the doubly linked list, the node contains data along with the next and previous part. The next part contains an address to the next node in the sequence and the previous part contains the address to the node before.

Diagram

 

Doubly Linked List

 

Circular Linked List

In a circular linked list, the last node of the list holds the address of the first node and hence forms a complete circle.

Diagram

 

circular linked list