codedamn

Linked List Data Structure in C++ Complete Guide (2022)

Linked List Data Structure in C++ Complete Guide (2022)

Whether you are preparing for an Interview or want to work as a Developer, knowing Data structures is a must pre-requisite for success. In this article, I will introduce you to the concept of a Data Structure known as a Linked List. A good knowledge of Linked List will help you to design and implement efficient solutions to programming problems.

List as a Data Structure

We can study any Data Structure in two ways i.e.,

  • As Mathematical Models Or Abstract Data Type (ADT)
    1. An abstract view of something means we define its features and operations of it without getting into how something works internally. For example – We all use Smart Phones and know what they can do and their functionalities but we don’t care about the details of their inner circuits.
    2. The List is an Abstract Data Type
  • Implementation in a High-Level Programming Language.
    1. Here we study in detail How something works. Learning about mobile circuits and hardware is a valid example here.
    2. There are many ways to implement a List in C++ like Arrays or the Linked List.

List as Abstract Data Type

A Static List

  • The number of elements we can add to the List is fixed.
  • We can store any element of a given data type.
  • We can write or modify an element at a specified position on the List.
  • Read Element at a particular position of the List.

An Array is an implementation of a Static List in C++

// An Array has fixed elements int static_List_Example[10]; // We can modify/add elements to an Array static_List_Example[3] = 7; // We can read elements at any position cout<<static_List_Example[3];
Code language: C++ (cpp)

The problem with Arrays is that size of an array does not grow as per our need in the program that’s why we want a dynamic List that is flexible enough to do it.

A Dynamic List

  • When the empty its size is taken as 0.
  • We can insert an element of any data type into the List.
  • We can remove elements at any specified position in the List.
  • We can read and modify an element at any position in the List.
  • We can count the Number of elements in the list

Although we can use Arrays itself to create a new Data structure that implements Dynamic List. But the operations are inefficient due to large time complexity.

Linked List is a better alternative and is the implementation of Dynamic List in C++.

Arrays

Arrays are contiguous blocks of memory. This means that all the blocks are put together by the Memory Manager.

Let’s understand this with an example.

Suppose we initialize an array named “toyNumber” and declare it with the size of 4

int toyNumber[4];
Code language: C++ (cpp)
Memory Management of Arrays in C++
Memory Management of Arrays in C++
  • Here X has already preoccupied a memory block. Now when we initialize an array that needs 4 Blocks they get accommodated before X.
  • But in the second case where we require 6 blocks of array elements, they are accommodated after X as in array elements are allocated continuous blocks of memory.
  • Due to this 4 Block of memory is wasted in the process in the second case.

Introduction to Linked List

In Linked List, memory to the list elements is not available in form of continuous blocks of memory fashion. Instead, each element of the list can be stored randomly anywhere in the memory.

This is possible because each element is a node. Each node not only stores the data but also stores the address of the next element as a link or reference to its memory space.

Let us take the previous example of “toyNumber” and create a list of 4 elements to understand syntax and memory Management in a Linked List.

class Node{ public: int data_item; Node* link; };
Code language: C++ (cpp)
Memory management of Linked List in C++

Arrays vs Linked List

ArraysLinked List
The Cost of accessing an element is constant or O(1)The cost of accessing an element is O(n)
Arrays have fixed sizes that can not be changed once specified.The size of the Linked List can be changed according to our needs.
Unused memory due to continuous allocation creates inefficiency.There is no unused memory as each node carries the link to the next element as its memory address.
The memory may be not available as one large block.The memory may be available as multiple small blocks.
The time complexity of inserting or deleting an element in the array is O(n), O(1) and O(n) at the beginning, end and at ith position respectively.The time complexity of inserting or deleting an element in the Linked List is O(1), O(n) and O(n) at the beginning, end and ith position respectively.
Comparative Analysis

Linked List: Implementation

The basic idea behind Linked List is to store Data in Nodes. These Nodes are Structures or Classes in C++. Each Node has two variables:

  • A variable to store data of required Data type. Let’s call this variable “data_item” for our example.
  • A variable to store the address to the next Node. Let’s call this variable “node_link”.
// Defining a Node in C++ class Node{ public: // Node stores a Integer type data element int data_item; // link is the pointer to the Node Node* link; };
Code language: C++ (cpp)

We then create a head pointer to Node. This pointer represents the entire Linked List. we will call it “head_node”.

// head_node is a pointer to a Node Node* head_node;
Code language: JavaScript (javascript)

We use the new keyword to create new Nodes as per needs. It returns the address of a newly created node in the List. Pointer variable stores this address. Let’s call this variable “temp”

// temp is a pointer to Node // temp stores address of new Node Node* temp = new Node();
Code language: JavaScript (javascript)

Now that we know how to create a Node and allocate memory for the new node. Let’s understand how to perform basic operations on the List.

Logical View of Linked List
Logical View of Linked List

Insertion in an Empty List

#include<bits/stdc++.h> using namespace std; // Class Node contains Data Element and Link to next Node. class Node{ public: int data_item; Node* link; }; // Main Function int main(){ // Creating First Node Pointer Node* head_Node; // Creating new Node Node* temp = new Node(); // Inserting Data temp -> data_item = 7; // You can also access data item as: *(temp.data_item); // Set link to NULL temp -> link = NULL; // Join first Node Pointer to new created Node. head_Node = temp; // Printing newly added data element. cout<< head_Node -> data_item; return 0; }
Code language: C/AL (cal)
Insertion in an empty List
Insertion in an empty List

Insertion at the end of a List

We use a While Loop to traverse a Linked List and add a new element at the end of the List. Let’s take an example of a List with 2 elements and we want to insert a third element.

#include<bits/stdc++.h> using namespace std; // Class Node contains Data Element and Link to next Node. class Node{ public: int data_item; Node* link; }; // Main Function int main(){ // Creating First Node Pointer Node* head_node; // Inserting 1st Element Node* temp = new Node(); temp -> data_item = 7; temp -> link = NULL; head_node = temp; cout<< "First Element Inserted: "<<head_node -> data_item<<"\n"; temp = new Node(); temp -> data_item = 11; temp -> link = NULL; // Inserting 2nd Element // Creating new node pointer temp1 for Traversal // Finding address of Last element of List Node* temp1 = head_node; while(temp1 -> link != NULL){ temp1 = temp1 -> link; } temp1 -> link = temp; cout<< "Second Element Inserted: "<<temp -> data_item<<"\n"; // Printing the Linked List cout<<"List: "; Node* temp2 = head_node; while(true){ cout<<temp2 -> data_item<<" "; if(temp2 -> link == NULL) break; temp2 = temp2 -> link; } return 0; }
Code language: C++ (cpp)
Insertion at end of List
Insertion at the end of the List

Insertion at the beginning of the List

#include<bits/stdc++.h> using namespace std; // Defining the Node of a List class Node{ public: int data_item; Node* link; }; Node* head_node; // Global declaration of head Node // Function to insert an element at beginning of List void insertElement(int x){ Node* temp = new Node(); temp -> data_item = x; temp -> link = head_node; head_node = temp; } // Function to Print List void printList(){ Node* temp = head_node; cout<<"List: "; while (temp != NULL){ cout<<temp -> data_item<<" "; temp = temp -> link; } cout<<"\n"; } // Main Function int main(){ head_node = NULL; int n; // Number of Element to enter cout<<"Enter Number of Elements to insert: "; cin>>n; for (int i=0;i<n;i++){ cout<<"Enter the Number: "; int number; cin>>number; insertElement(number); printList(); } return 0; }
Code language: C++ (cpp)
Insertion at thee beginning of List
Insertion at the beginning of the List

Insertion at the Nth position

To insert a node at the Nth Position, we have to first traverse to the n-1 position in the List and then:

  1. Link the Newly created Node to the Nth Position Node
  2. Then Link the (N-1)th Node to the newly created Node.
#include<bits/stdc++.h> using namespace std; // Defining the Node class Node{ public: int data_item; Node* link; }; Node* head_node; // Function to Insert element at Nth Position void insertElement(int number, int position){ Node* temp1 = new Node(); temp1 -> data_item = number; temp1 -> link = NULL; if(position == 1){ temp1 -> link = head_node; head_node = temp1; return; } Node* temp2 = head_node; for (int i=0;i<position-2;i++){ temp2 = temp2 -> link; } temp1 -> link = temp2 -> link; temp2 -> link = temp1; } // Function to Print the List void printList(){ Node* temp = head_node; cout<<"List is: "; while(temp != NULL){ cout<<temp -> data_item<<" "; temp = temp -> link; } } int main(){ head_node = NULL; // insert 4 at 1st Position insertElement(4,1); // insert 7 at 2nd Position insertElement(7,2); // insert 23 at 3rd Position insertElement(23,3); // insert 31 at 4th Position insertElement(31,4); // Print the Linked List printList(); return 0; }
Code language: C++ (cpp)
Insertion at Nth position in a List
Insertion at Nth position in a List

Deletion in List

To delete a node from the Nth List we need to traverse to the (N-1)th position in the List and then

  1. Link the Nth position to the (N+1)th position
  2. free the memory of the Nth position element using the free keyword.
#include<bits/stdc++.h> using namespace std; // Defining the Node class Node{ public: int data_item; Node* link; }; Node* head_node; // Function to Insert element at end Position void insertElement(int number){ Node* temp1 = new Node(); temp1 -> data_item = number; temp1 -> link = NULL; if(head_node == NULL){ head_node = temp1; return; } Node* temp2 = head_node; while (temp2 -> link != NULL){ temp2 = temp2 -> link; } temp2 -> link = temp1; } // Function to Print the List void printList(){ Node* temp = head_node; while(temp != NULL){ cout<<temp -> data_item<<" "; temp = temp -> link; } } // Function to delete an element from Nth Postion void deleteElement(int position){ Node* temp1 = head_node; if (position == 1){ head_node = temp1 -> link; free(temp1); return; } for (int i=0;i<position-2;i++){ temp1 = temp1 -> link; } Node* temp2 = temp1 -> link; temp1 -> link = temp2 -> link; free(temp2); } int main(){ // Empty List head_node = NULL; // Insert Elements at the end of List insertElement(4); insertElement(7); insertElement(23); insertElement(31); // Print the Linked List cout<<"List before Deletion: "; printList(); int position; cout<<"\nEnter position to delete element: "; cin>>position; // delete element from given position deleteElement(position); // Print List after Deletion cout<<"\nList after Deletion: "; printList(); return 0; }
Code language: C++ (cpp)
Deletion in a List
Deletion in a List

Doubly Linked List

In the Doubly Linked List, each Node has two links. One to its next Node and one to its previous Node. If a pointer is pointing to a node in our List then, we can access both the next and previous elements to that Node through Doubly Linked List.

Logical View of Doubly Linked List
Logical View of Doubly Linked List

Doubly Linked List: Implementation

#include<bits/stdc++.h> using namespace std; // Defining a Doubly Linked List Node class Node{ public: int data_item; // Pointer to Previous Node Node* prev_link; // Pointer to Next Node Node* next_link; }; Node* insert_Node(int x){ Node* temp = new Node(); temp -> data_item = x; temp -> prev_link = NULL; temp -> next_link = NULL; return temp; } // Global head Node to represent List Node* head_node; // Function to insert new Node at beginning void insertAtStart(int x){ Node* new_node = insert_Node(x); if (head_node == NULL){ head_node = new_node; return; } head_node -> prev_link = new_node; new_node -> next_link = head_node; head_node = new_node; } // Print Function void printFwdList(){ Node* temp = new Node(); temp = head_node; cout<<"Forward List is: "; while(temp != NULL){ cout<<temp -> data_item<<" "; temp = temp -> next_link; } cout<<"\n"; } // Function to print List in reverse order void printReverseList(){ Node* temp = new Node(); temp = head_node; // If List is empty if (temp == NULL) return; // Going to Last Node while (temp -> next_link != NULL){ temp = temp -> next_link; } // Traversing back in reverse order cout<<"Reverse List is: "; while(temp !=NULL){ cout<<temp -> data_item<<" "; temp = temp -> prev_link; } cout<<"\n"; } // Main Function int main(){ head_node = NULL; // insert 7 in the List insertAtStart(7); // insert 11 in the List insertAtStart(11); // insert 19 in the List insertAtStart(19); // insert 23 in the List insertAtStart(23); // Printing List in Forward Direction printFwdList(); // Printing List in Reverse Order printReverseList(); return 0; }
Code language: C++ (cpp)
Implementation of Doubly Linked List
Implementation of Doubly Linked List

Conclusion

A linked List is an important Data Structure. It let us add elements dynamically as the program executes. But each Node of the List consumes more memory than a single element in an Arrays. So you must examine what the problem requires and use the appropriate Data Structure.

Your next step should be to practice Questions on Linked List and get comfortable with using pointers and new and free keywords.

Learn programming on codedamn

Codedamn is an interactive coding platform with tons of sweet programming courses that can help you land your first coding job. Here's how:

Programming is one of the most in-demand jobs today. Learning to program can change your future. All the best!

Sharing is caring

Did you like what Aviral Sharma wrote? Thank them for their work by sharing it on social media.