DATA STRUCTURES | LEVEL 2 | LAB 3
Linked List (Part I)
1- What is the Liked List?
A linked list is a data structure that can store an indefinite amount of items. These items are
connected using pointers in a sequential manner.
Every element contains some data and a link to the next element.
The elements of a linked list are called the nodes. A node has two fields i.e. data and next.
The data field contains the data being stored in that specific node.
The next field contains the address of the next node.
Class Node
{
int data;
Node *next;
};
2- Linked List Operations:
1) Insert element in the Beginning.
2) Insert element to the End (Append).
3) Insert element in Particular Position.
4) Traverse (Display) Linked List.
5) Delete element from the Beginning.
6) Delete element from the End.
7) Delete Element from Particular Position.
8) Find Element (Search).
1|Page
DATA STRUCTURES | LEVEL 2 | LAB 3
Linked List Code ( Part I):
#include<iostream>
using namespace std;
void main ();
class Node
{
int data;
Node *next;
};
class LinkedList { // Define the linked list class
Node* head; // Pointer to the first node in the list
public:
LinkedList() { // Constructor initializes head to NULL
head=NULL;
}
void InsertB(int item)//Insert to Begin
{
Node * newnode = new Node; //(1)Create new node
newnode->data = item; //(2)Fill the Data
newnode->next = head; //(3)Link to old list
head = newnode; //(4)Move start pointer to new node
}
void InsertE(int item) //Insert to End
{
Node * newnode = new Node;
newnode->data = item;
newnode->next=NULL;
if(head == NULL) //List is Empty
{
head = newnode;
}
else // List is not Empty
{
Node *Temp=head;
while (Temp->next !=NULL)
{
Temp = Temp->next;
}
Temp->next= newnode;
}
}
2|Page
DATA STRUCTURES | LEVEL 2 | LAB 3
void InsertAt(int item, int pos) // Insert in particular position
{
int curr = 1;
Node *newnode = new Node;
newnode->data = item;
newnode ->next = NULL;
if( head == NULL){ // list is empty
head = newnode;
}
else if (pos == 1){ // first position to be head node
newnode->next = head;
head = newnode;
}
else
{
Node *temp = head;
while (curr < pos-1){
curr++;
temp=temp->next;
}
newnode->next = temp->next;
temp->next = newnode;
}
}
void traverse() //Display Linked List
{
if(head == NULL)
{
cout<<"Empty List \n";
}
Node * Temp = head;
cout<<"Elements in Linked List\n";
while(Temp != NULL)
{
cout<<Temp->data<<" ";
Temp = Temp->next;
}
cout<<endl;
}
};
3|Page
DATA STRUCTURES | LEVEL 2 | LAB 3
int main()
{
LinkedList l;
l.InsertB(10);
l.InsertE(30);
l.InsertB(5);
l.InsertAt(20,2);
l.traverse();
//or
char choice;
int item,pos;
while(true){
cout<<"\t*********************************************"<<endl;
cout<<"\t\tEnter (B) to insert new item in the beginning \n";
cout<<"\t\tEnter (E) to insert new item to the End \n";
cout<<"\t\tEnter (A) to insert at a certain position\n";
cout<<"\t\tEnter (T) to View All items \n";
cout<<"\t\tEnter (Z) to Exit \n";
cout<<"\t*********************************************"<<endl;
cout<<"Your Choice:";
cin>>choice;
switch (choice)
{
case 'b':case 'B':
{cout<<"Please Enter the item: ";
cin>>item;
l.InsertB(item);
break;}
case 'e':case 'E':
{cout<<"Please Enter the item: ";
cin>>item;
l.InsertE(item);
break;}
case 'a':case'A':
{ cout<<"Enter the value ";
cin>>item;
cout<<"Enter the position \n";
cin>>pos;
l.InsertAt(item,pos);break;}
case't':case'T': l.traverse();break;
case'z':case'Z':exit(0);
} }
return 0;
4|Page
DATA STRUCTURES | LEVEL 2 | LAB 3
Output:
Assignment #5:
Complete the following Operations to Linked List Program:
1. Insert node at position.
2. Delete first Node.
3. Search for Element.
Bonus:
4. Delete last Node.
5. Update Node Value.
By using Function for each operation
5|Page
