Linked Lists

A Linked list is a linear data structure, where the linear order is given by means of pointers. Each element of the linked list is known as nodes.

Each node is divided into two parts:

- The first part contains the data of the element.
- The second part contains the address of the next node in the list (next).

## Traversing a Linked List in C++

Traversing is the process of displaying all the elements of the linked list. Here, we have traversed the elements of the linked list using functions.

#include <iostream>

using namespace std;

struct node{

int data;

struct node*next;

};

void traversal(struct node*ptr);

int main()

{

struct node*head,*second,*third;

head=new node();

second=new node();

third=new node();

head->data=7;

head->next=second;

second->data=14;

second->next=third;

third->data=21;

third->next=NULL;

node *newnode;

newnode=new node();

traversal(head);

cout<<"n Insert element:";

cin>>newnode->data;

newnode->next=head;

head=newnode;

traversal(head);

return 0;

}

void traversal(struct node*ptr)

{ while(ptr!=NULL)

{

cout<<ptr->data<<" ";

ptr=ptr->next;

}

}

## Algorithm for traversing a Linked List

The variable ptr points to the node currently being processed. The variable head contains the address of the head node of the LIST.

void traversal(struct node*ptr)

1.ptr=head (Initialize pointers)

2. Repeat steps 3 and 4 while PTR!= NULL

3. Apply the PROCESS to data[PTR].

4. Set ptr=next[PTR]5. Exit

## Insertion in a Linked List in C++

Output:

Enter data:56

Do you want to insert another number? (y/n)y

Enter data:23

Do you want to insert another number? (y/n)y

Enter data:96

Do you want to insert another number? (y/n)n

Elements in Linked list: 56 23 96

## Insertion into a Linked List in C++

#include<iostream>

using namespace std;

struct node{

int data;

node*next;

};

int main()

{

char ch;

node *head,*newnode,*temp;

head = NULL;

do

{

newnode=new node();

cout<<"n Enter data:";

cin>>newnode->data;

newnode->next=NULL;

if(head==NULL)

head=temp=newnode;

else

{

temp->next=newnode;

temp=newnode;

}

cout<<"n Do you want to insert another number? (y/n)";

cin>>ch;

}while(ch=='y');

temp=head;

cout<<"n Elements in Linked list: ";

while(temp!=NULL)

{

cout<<temp->data<<" ";

temp=temp->next;

}

return 0;

}

## Deletion from a Linked List

Output:

Elements of linked list: 7 14 21After Deletion

Elements of linked list:14 21

#include <iostream>

using namespace std;

struct node{

int data;

struct node*next;

};

void traversal(struct node*ptr);

int main()

{

struct node*head,*second,*third;

head=new node();

second=new node();

third=new node();

head->data=7;

head->next=second;

second->data=14;

second->next=third;

third->data=21;

third->next=NULL;

cout<<”n Elements of linked list:”;

traversal(head);

cout<<"n After Deletionn";

cout<<”n Elements of linked list:”;

struct node*temp;

temp=head;

head=head->next;

free(temp);

traversal(head);

return 0;

}

void traversal(struct node*ptr)

{ while(ptr!=NULL)

{

cout<<ptr->data<<" ";

ptr=ptr->next;

}

}