A Brief Introduction to Linked Lists

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

A Linked List is a linear Data Structure, which consists of a group of nodes, which are stored at random addresses. Each node consists of 2 parts:

  • Data: The Data which is stored at the particular address.
  • Reference: The address of the next node of the linked list.

Linked List Representation

Why Linked List?

Although using arrays, we can store the same types of data; we can access elements directly using the index; however, they have the following drawbacks.

1) The arrays have a fixed size : As a result, we must know the maximum amount of elements ahead of time. In addition, regardless of use, the allotted memory is always equal to the maximum limit.
2) Inserting a new element into an array at some middle position is costly since space must be made for the new elements, and old elements must be shifted to make room.
3) Also deleting an element from an array is costly as it too requires shifting of array elements.

Advantages of Linked List

  • Dynamic Data Structure: Linked List being a dynamic data structure can shrink and grow at the runtime by deallocating or allocating memory. So, there is no need for an initial size.

  • No Memory Wastage: As the size of a linked list can grow or shrink at runtime, so there is no memory wastage. Only the required memory is allocated.

  • Implementation: Some very helpful data structures like queues and stacks can easily be implemented using a Linked List.

  • Insertion and Deletion Operation: In a Linked List, insertion and deletion operations are quite easy, as there is no need to shift every element after insertion or deletion. Only the address present in the pointers needs to be updated.

Disadvantages of Linked List

  • Memory Usage: The memory required by a linked list is more than the memory required by an array, as there is also a pointer filed along with the data field in the linked list. The pointer field too requires memory to store the address of the next node.

  • Random Access: To access node an at index x in linked list, we have to traverse through all the nodes before it. In case of an array, we can directly access an element at index x using arr[x].

  • Reverse Traversal: In a singly linked list, reverse traversal is not possible, as every node stores only the address of the next node. But in case of a doubly-linked list, reverse traversal is possible, but it consumes more memory, as we have to allocate extra memory to store the previous pointer.

Types of Linked Lists

Singly Linked List

In a Singly Linked List, each node contains:

  • A data field.
  • A address field, which points to the next node.

Singly Linked List Node Structure

class Node{
public:
	int data;
	Node* next;
};

Doubly Linked List

In a Doubly Linked List, each node contains:

  • A data field.
  • Two address field next and prev, next points to the immediate next node in the linked list and prev points to the immediate previous node in the linked list.

Doubly Linked List Node Structure

class DLLNode{
public:
	int data;
	DLLNode* next;
        DLLNode* prev;
};

Circular Linked List

In a Circular Linked List, instead of pointing to NULL, the last node points to the head of the linked list. Hence, the name circular linked list The main advantage of a circular linked list is that we can consider any node as the starting node and traverse the list.

Node Structure

class Node{
public:
	int data;
	Node* next;
};

So, in this article, we gave you a brief introduction to Linked Lists. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Binary search on Linked List
Next post Delete a node in Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *