Linked Lists Data Structure in C++

Linked lists are fundamental data structures widely used in computer science and programming. In this comprehensive guide, we’ll delve into the world of linked lists, covering their definition, types, operations, and practical implementations. Whether you’re a beginner exploring data structures or a seasoned developer looking to deepen your understanding, this guide will equip you with the knowledge and skills to master linked lists effectively.

Understanding Linked Lists:

A linked list is a linear data structure consisting of nodes connected by pointers or references. Unlike arrays, linked lists do not require contiguous memory allocation and can dynamically adjust their size. Each node in a linked list contains data and a reference to the next node, forming a sequence of elements.

What is Node ?

A node is a fundamental building block of a linked list. It mainly contains two components:

1. Data: The actual value or payload stored in the node.
2. Next Pointer: A reference or pointer to the next node in the sequence.

The Head of a Linked List ?

The head is a special node that serves as the starting point or entry point of a linked list. It contains the reference to the first node in the list. By accessing the head node, we can traverse the entire linked list by following the pointers to subsequent nodes.

Types of Linked Lists:

There are several types of linked lists, including:

1. Singly Linked List:

Each node has a reference to the next node in the sequence, allowing traversal in one direction only.

# include <iostream>
using namespace std;

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

How To Create Singly Linked List :

// Defining the Methods
class SinglyLinkedList {
 public:
  Node *head;
  LinkedList(int Arr[], int n); // Contructor
  void Insert(int num, int index);
  void Traversal();
  void Delete(int index);
  int Searching(int index);
};

// To Create Linked List
SinglyLinkedList::LinkedList(int Arr[], int n){
 head = new Node;
 head -> data = NULL;
 head -> next = NULL;
 Node *last = head; // We will not touch head thats why we create "last", now-on we will do changes on "last"
 
 for(int i=0; i < n; i++){ 
  last -> next = new Node; // First it will create new space for new node addr
  last -> next -> data = Arr[i]; // then it will store data into its data variable
  last -> next -> next = NULL; // then it will make the next variable there as NULL and create new NODE there in the next round.
  last = last -> next;
 }
}

2. Doubly Linked List:

Each node has references to both the next and previous nodes, allowing traversal in both directions.

# include <iostream>
using namespace std;

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

How to Create Doubly Liked List :

class DoubleLinkedList{
 private:
  Node *head , *last;
 public:
  DoubleLinkedList(int Arr[], int count);
  void Traversal();
  void reversal();
  int push_back(int newData);
  int push_front(int newData);
  int pop();
  int peek();
};

DoubleLinkedList::DoubleLinkedList(int Arr[], int count){
 head = new Node;
 head -> data = NULL;
 head -> prev = NULL;
 head -> next = NULL;
 last = head;
 
 for(int i=0; i < count; i++){
  Node *newNode = new Node;
  newNode -> data = Arr[i];
  newNode -> prev = last;
  last -> next = newNode;
  newNode -> next = NULL;
  last = last -> next;
 }
}

Basic Operations on Linked Lists:

Common operations performed on linked lists include:

Some Operations For Singly Linked List :

void SinglyLinkedList::Traversal(){
 Node *q = head;
 while(q -> next){
  cout << q -> next -> data << endl;
  q = q -> next;
 }
}

void SinglyLinkedList::Insert(int num, int index){
 Node *prev = head;
 Node *newNode = new Node;
 newNode -> next = NULL;
 newNode -> data = num;
 
 for(int i=0; i < index; i++){
  prev = prev -> next;
 }
 Node *tmp = prev -> next;
 prev -> next = newNode;
 newNode -> next = tmp;
 cout << "Data inserted .... " << endl;
}

void SinglyLinkedList::Delete(int index){
 Node *Q = head;
 for(int i=0; i < index; i++){
  Q = Q -> next;
 }
 Node *n = Q -> next;
 Q -> next = n -> next;
 delete n;
 cout << "Delete the number from LinkedList" << endl;
}

int SinglyLinkedList::Searching(int index){
 Node *q = head;
 for(int i=0; i <= index; i++){
  q = q -> next;
 }
 return q -> data;
}

Some Operations For Doubly Linked List :

void DoubleLinkedList::traversal(){
 Node *tmp = head;
 cout << "Forwarding Display...." << endl;
 while( tmp -> next != NULL ){
  cout << tmp -> next -> data << endl;
  tmp = tmp -> next;
 } 
}

void DoubleLinkedList::reversal(){
 Node *tmp = last;
 cout << "Reversing Display .... " << endl;
 while( tmp -> prev != NULL ){
  cout << tmp -> data << endl;
  tmp = tmp -> prev;
 }
}

int DoubleLinkedList::push_back(int newData){
 Node *q = new Node;
 q -> data = newData;
 q -> next = NULL;
 q -> prev = last;
 last -> next = q;
 last = q;
 return newData;
}

int DoubleLinkedList::push_front(int newData){
 Node *p = new Node;
 p -> data = NULL;
 p -> prev = NULL;
 p -> next = head;
 head -> data = newData;
 head -> prev = p;
 head = p;
 return newData;
}

int DoubleLinkedList::pop(){
 Node *L = last;
 int tmp = last -> data;
 last -> prev -> next = NULL;
 last = last -> prev;
 delete L;
 return tmp;
}

int DoubleLinkedList::peek(){
 return last -> data;
}

1. Insertion: Adding a new node at the beginning, end, or middle of the list.
2. Deletion: Removing a node from the list based on its position or value.
3. Traversal: Iterating through the list to access and process each node’s data.
4. Searching: Finding a specific node or value within the list.
5. Reversal: Changing the order of nodes in the list to reverse its sequence.
6. Push_Back : Inserting a new node at the end of the list.
7. Push_Front : Inserting a new node at the beginning of the list.
8. Pop : Removing the last node from the list.
9. Peek : Getting the last node from the list.

Best Practices and Considerations:

When working with linked lists, it’s essential to consider:

1. Memory Management: Proper memory allocation and deallocation to avoid memory leaks.
2. Efficiency: Optimize operations for time and space complexity, especially in performance-critical applications.
3. Error Handling: Handle edge cases and errors gracefully to ensure robustness and reliability.
4. Testing: Thoroughly test linked list implementations to validate correctness and identify potential bugs.

Conclusion:

Linked lists are versatile and powerful data structures with diverse applications in software development and computer science. By understanding the fundamentals, types, operations, and practical implementations of linked lists, developers can leverage their flexibility and efficiency to solve a wide range of problems effectively. Whether you’re building algorithms, designing data structures, or optimizing memory management, mastering linked lists is an essential skill for any programmer.