Linked List Data Structure

C Programming, CPP Programming, JAVA, Python / By

Linked List Data Structure:

A linked list is a type of data structure that consists of a chain of nodes, each of which contains a value and a pointer to the next node in the chain.

The list’s head pointer points to the first node, and the list’s last element points to null. The head pointer points to null when the list is empty.

Linked lists can grow in size dynamically, and inserting and deleting elements from them is simple because, unlike arrays, we only need to change the pointers to the previous and next elements to insert or delete an element.

Linked lists are commonly used in the construction of file systems, adjacency lists, and hash tables.

Why Linked List?

Arrays can be used to store similar types of linear data, but they have the following limitations.
1) Because the array size is fixed, we must know the maximum number of elements in advance. Furthermore, regardless of usage, the allocated memory is always equal to the upper limit.
2) Inserting a new element in an array of elements is expensive because room must be made for the new elements, and existing elements must be shifted to make room, whereas in a linked list if we have the head node, we can traverse to any node through it and insert a new node at the required position.

Advantages of Linked Lists over arrays

1)Dynamic Data Structure:

  • Because the linked list is a dynamic data structure that can shrink and grow at runtime by deallocating or allocating memory, there is no need for initial size.
  • In contrast, in an array, an initial size must be declared, and the number of elements cannot exceed that size.

2) No Memory Wastage:

  • There is no memory waste because the size of a linked list can grow or shrink at runtime. Only the necessary memory is allocated.
  • In arrays, we must first initialize it with a size that we may or may not fully utilize. Thus, memory waste may occur.

3)Implementation:

A Linked List can be used to easily implement some very useful data structures such as queues and stacks.

4)Insertion and Deletion Operation:

Insertion and deletion operations in a Linked List are simple because there is no need to shift every element after insertion or deletion. Only the address in the pointers needs to be changed.

Disadvantages of Linked Lists over arrays

1)Memory Usage:

A linked list requires more memory than an array because it includes a pointer field in addition to the data field. The pointer field, like all other fields, requires memory to store the address of the next node.

2)Random Access:

To get to node an at index x in a linked list, we must first go through all the nodes before it. In the case of an array, however, we can use arr[x] to directly access an element at index x.

3)Reverse Traversal:

  • Reverse traversal is not possible in a singly linked list because each node stores only the address of the next node. Reverse traversal is possible in the case of a doubly-linked list, but it consumes more memory because we must allocate extra memory to store the previous pointer.
  • With the help of a for loop, we can perform a simple reverse traversal in arrays.

Representation:

A pointer to the first node of a linked list is used to represent it. The first node is referred to as the head. When the linked list is empty, the value of the head is NULL.
A list node is made up of at least two parts:
1) data (we can store integers, strings, or any type of data).
2) A pointer to the next node (or a reference to it) (connects one node to another)

Example Node of a Linked List