-singly linked list c++ -singly linked list code -singly linked list in data structure -Data structure and algorithm –Data structure and algorithm in C++ – Data structure using C++ -Data structure projects in C++ – Data structure Project idea -Data structure MCQ -Data structure Interview Question –data structure question paper –free course online –past papers -final year projects for computer science with source code -semester project ideas -computer programming -computer science interview questions- tutorial -cui
Single Link list using c++
Link List is a Data Structure in which elements are explicitly ordered, that is each item contains within itself the address of next item.
The array implementation has the serious drawback and that is we must specify size at the construction time though it is simple and fast.
Create a structure called a Node
The object field will hold the actual list element.
The next field in the structure will hold the location(Address) of the next node.
Chain the nodes together to form a linked list.
A very common source of problems in program maintenance is the need to increase the capacity of a program to handle larger collections.
In a linked list, each item is allocated space as it is added to the list. A link is kept with each item to the next item in the list.
Each node of the list has two elements:
- The item being stored in the list
- A pointer to the next item in the list
The last node in the list contains a NULL pointer to indicate that it is the end or tail of the list.
As items are added to a list, memory for a node is dynamically allocated. Thus the number of items that may be added to a list is limited only by the amount of memory available.
struct node
{
char name[15];
node *next;
};
Applications of a singly linked list?
- Used to implement Stacks , Queues, Graphs, Hash Tables.
- Undo functionality in Photoshop or Word.
- A polynomial can be represented in an array or in a linked list by simply storing the coefficient and exponent of each term.
- Linked lists are useful for dynamic memory allocation.
Inserting to a Link List :
The simplest strategy for adding an item to a list is to:
- Allocate space for a new node.
- Copy the item value into it.
- Make the new node’s next pointer point to the current head of the list and
- Make the head of the list point to the newly allocated node.
This strategy is fast and efficient but each item is added to the head of the list.
Searching a Link List:
To search a list of n objects or elements the search function takes n operations to search a data item in the LL in worst case, since it may have to search the entire link list.
Deletion from Link List
This removes a data item’s node (block) from the start of link list. Pointer must be pointing to that node which has to be deleted and then pointer will have to be updated.
But if we wish to delete the particular node (block) with given key to match, then we have to search for that node (block) in the entire Link List.
C++ Code for Single Link list
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class list
{
struct node
{
int data;
node *link;
} *p;
public:
void inslast(int);
void insbeg(int);
void delelement(int);
void delbeg();
void dellast();
void disp();
int seek(int);
list()
{
p = NULL;
}
~list();
};
void list::inslast(int x)
{
node *q, *t;
if (p == NULL)
{
p = new node;
p->data = x;
p->link = NULL;
}
else
{
q = p;
while (q->link != NULL)
q = q->link;
t = new node;
t->data = x;
t->link = NULL;
q->link = t;
}
cout << “\nInserted Successfully at the end…”;
disp();
}
void list::insbeg(int x)
{
node *q;
q = p;
p = new node;
p->data = x;
p->link = q;
cout << “\n Inserted successfully at the beginning . .”;
disp();
}
void list::delelement(int x)
{
node *q, *r;
q = p;
if (q->data == x)
{
p = q->link;
delete q;
return;
}
r = q;
while (q != NULL)
{
if (q->data == x)
{
r->link = q->link;
delete q;
return;
}
r = q;
q = q->link;
}
cout << “\nElement you entered ” << x << ” is not found..”;
}
void list::delbeg()
{
cout << “\nThe list before deletion:”;
disp();
node *q;
q = p;
if (q == NULL)
{
cout << “\nNo data is present..”;
return;
}
p = q->link;
delete q;
return;
}
void list::dellast()
{
cout << “\n The list before deletion: “;
disp();
node *q, *t;
q = p;
if (q == NULL)
{
cout << “\nThere is no data in the list..”;
return;
}
if (q->link == NULL)
{
p = q->link;
delete q;
return;
}
while (q->link->link != NULL)
q = q->link;
q->link = NULL;
return;
}
list ::~list()
{
node *q;
if (p == NULL)
return;
while (p != NULL)
{
q = p->link;
delete p;
p = q;
}
}
void list::disp()
{
node *q;
q = p;
if (q == NULL)
{
cout << ” \nNo data is in the list..”;
return;
}
cout << ” \nThe items present in the list are :”;
while (q != NULL)
{
cout << ” ” << q->data;
q = q->link;
}
cout <<endl;
}
int list::seek(int value)
{
node *temp;
temp = p;
int position = 0;
while (temp != NULL)
{
if (temp->data == value)
return position + 1;
else
{
temp = temp->link;
position = position + 1;
}
}
cout << ” Element ” << value << ” Not Found”;
return 0;
}
int main()
{
list l;
int ch, v, p, ps;
do
{
cout << “\nOperations on List.. \n”;
cout << “\n1. Insertion\n2. Deletion\n3. Display\n4. Seek\n5. Exit”;
cout << “\nEnter your choice: “;
cin >> ch;
switch (ch)
{
case 1:
cout << “\n1. Insertion at the beginning\n2. Insertion at the end”;
cout << “\n3. Enter your choice:”;
cin >> ps;
cout << “\nEnter the value to insert: “;
cin >> v;
switch (ps)
{
case 1:
l.insbeg(v);
break;
case 2:
l.inslast(v);
break;
default:
cout << “\nThe choice is invalid..”;
return 0;
}
break;
case 2:
cout << “\n1. Delete the first element\n2. Delete the last element”;
cout << “\n 3 Enter the element to delete from list”;
cout << “\nEnter your choice: “;
cin >> ps;
switch (ps)
{
case 1: l.delbeg();
cout << “\nThe list after deletion: “;
l.disp();
break;
case 2: l.dellast();
cout << “\nThe list after deletion”;
l.disp();
break;
case 3:
l.disp();
cout << “\nEnter the element to delete :”;
cin >> v;
l.delelement(v);
cout << “\nThe list after deletion: “;
l.disp();
break;
default:
cout << “\nThe option is invalid..”;
break;
}
break;
case 3:
l.disp();
break;
case 4:
l.disp();
cout << “\nEnter the element to search: “;
cin >> v;
cout << “\nThe position of the element ” << v << ” is ” << l.seek(v);
//write system pause here
break;
case 5:
exit(1);
default:
cout << “\nThe option is invalid..”;
return 0;
}
//write system pause here
} while (ch != 5);
//write system pause here
return 0;
}
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#singly linked list c++ #singly linked list code #singly linked list in data structure#Data structure and algorithm #Data structure and algorithm in C++ # Data structure using C++ #Data structure projects in C++ # Data structure Project idea #Data structure MCQ #Data structure Interview Question #data structure question paper #free course online #past papers #final year projects for computer science with source code #semester project ideas #computer programming #computer science interview questions# tutorial #cui
#courses #pastpaper #Finalyearproject #tutorial #cui #project #programming #computer science
