Linked list with C++ Code Implementatio

A linked list is a list type data structure that contains a collection of data elements where the order of physical arrangement (memory allocated) is not continuous i.e. unlike in an array where the physical arrangement (memory allocated) is continuous.

In the linked list, each data element is represented by a node
A typical representation of a node of a singly linked list (explained below) is given below.

Hence we can represent a linked list as a collection of such nodes.


Types of Linked List :

a) Singly linked list 
b) Doubly linked list
c) Circular linked list

In this article, we will be discussing the singly linked list, doubly linked list and the circular linked list will be discussed in subsequent articles.

A. Singly-linked list 

A singly linked is a list where each node except the last has the address of its next
node and last node points to NULL.

We can implement a linked list with the help of structures(keyword struct) or a
class with a pointer (head) of the type that is of the node, which stores the link (address) to the starting of the list which is then iterated till we reach the node with Null.

Representation :

  

Operations in a singly linked list

Let's consider a linked list consisting of 5 elements, the head is pointing to A0


1. Traversal: 
we travel through each element linearly to reach any node. We have to traverse all the nodes before it until and unless we have the address of that node.
Search and traversal operation takes O(n) 

2. Insertion at any point : 
 To insert a node X between A1 and A2, we need to traverse till A1,  
X.next = A1.next 
A1.next = X

3. Deletion at any point :
To delete a node A2, we need to traverse till A1
A1.next = A2.next
free(A2)

  • Video Explanation: 


Implementation Code for Single Linked List:


#include <bits/stdc++.h>
using namespace std;

void insert(int x, int pos);
void print(struct node *temp);

struct node {
int data;
struct node *next;
} *head = NULL;

int main() {
int i;
int n; // Number of element you want
//to insert in the linked list
cin >> n;
int num;
for (i = 1; i <= n; i++) {
cin >> num;
insert(num, i);
}
print(head);
return 0;
}
void insert(int x, int pos) {
struct node *nnode;
nnode = (struct node *)malloc(sizeof(struct node));
struct node *temp = head;
nnode->data = x;
if (head == NULL) {
temp = nnode;
nnode->next = NULL; // this is last node so its next->NULL
head = nnode; // here head is assigned to first node as of now which
// will help us to iterate through list
} else {
int i = 1;
while (i != pos - 1) {
i++;
temp = temp->next;
}
if (temp->next == NULL) {
nnode->next = NULL;
temp->next = nnode;
} else {
nnode->next = (temp->next)->next;
temp->next = nnode;
}
}
}

void print(struct node *temp) {
while (temp != NULL) {
cout << temp->data << "->";
temp = temp->next;
}
cout << endl;
}

Hand simulation of the code:





Hoping that you understood singly Linked List, here are some problems for you:

BASICS Problems :

      1. Print the elements of the linked list
      2. Insert a node at the tail of a linked list
      3. Insert a node at a specific position
      4. Delete a node
      5. Reverse a linked list

In the next article, we will be discussing the doubly linked list.
If you have any doubt or any suggestions please comment below

Thank You for Reading

Related Posts



If you like Learn DSA and would like to contribute please mail your article to info.learndsa@gmail.com and see your article appearing on the Learn DSA main page and help other.