Single link list C++

-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 onlinepast 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

Node
node single link list

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.

Singly link list
single link list data structure

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.

singly link list
delete in singly link list

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:

  1. Allocate space for a new node.
  2. Copy the item value into it.
  3. Make the new node’s next pointer point to the current head of the list and
  4. 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. 

singly link list
insertion in singly link 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.

Singly link list
delete in singly 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

Search within CuiTutorial

Scroll to Top