Showing posts with label Linked Lists. Show all posts
Showing posts with label Linked Lists. Show all posts

C++ example of Linked List implementation

It is debatable if Linked lists are needed in C++, especially because STL can do a very good job for the same functionality for which Linked Lists are required. Nevertheless sometimes it maybe convenient to know linked lists.



//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include <iostream>
#include <string>
#include <istream>
#include <limits>

using namespace
std;

class
Node
{

public
:
Node() : next(NULL) {}; //default constructor
Node(const string& s1) : info(s1), next(NULL) {};
string info;
Node* next;
};


Node* getNewNode()
{

//Lets flush the input buffer first
istream& in(cin);
in.ignore( numeric_limits<std::streamsize>::max(), '\n' );

//Read the String from console
cout<<"\tEnter a string: ";
istreambuf_iterator<char> eos; // end-of-range iterator
istreambuf_iterator<char> iit (cin.rdbuf()); // stdin iterator
string s2;
while
(iit!=eos && *iit!='\n') s2+=*iit++;

//Call the constructor with the input string
Node* newNode = new Node(s2);

return
newNode;
}


int
main()
{

Node* head = NULL;
bool
contFlag = true;
char
c;

while
(contFlag)
{

cout<<"\n\n";
cout<<"0. Quit"<<endl;
cout<<"1. Traverse and Print"<<endl;
cout<<"2. Insert node at the start"<<endl;
cout<<"3. Insert node at the end"<<endl;
cout<<"4. Insert after specified number of nodes"<<endl;
cout<<"5. Remove node from the start"<<endl;
cout<<"6. Remove node from the end"<<endl;
cout<<"7. Remove node from a specified number"<<endl;

cout<<"\nEnter your choice: ";
cin>>c;

switch
(c)
{

case
'0':
contFlag = false;
break
;
case
'1':
{

Node* tempNode = head;
int
count = 0;
while
(tempNode)
{

cout<<"\tItem "<<count<<" = "<<tempNode->info<<endl;
tempNode = tempNode->next;
count++;
}
}

break
;
case
'2':
{

Node* newNode = getNewNode();
newNode->next = head;
head = newNode;
}

break
;
case
'3':
{

Node* newNode = getNewNode();

Node* endNode = head;
if
(endNode)
{

while
(endNode->next)
endNode = endNode->next;
endNode->next = newNode;
}

else
//In case its the first element
{
head = newNode;
}
}

break
;
case
'4':
{

Node* tempNode = head;
if
(tempNode)
{

unsigned
num;
cout<<"\tInsert after how many nodes? : ";
cin>>num;
Node* newNode = getNewNode();

unsigned
count = 1;
//If less elements are present then insert at the end
while(tempNode->next && (count < num))
{

tempNode = tempNode->next;
count++;
}

newNode->next = tempNode->next;
tempNode->next = newNode;
}

else

{

cout<<"\tNo nodes present yet"<<endl;
}
}

break
;
case
'5':
{

Node* firstNode = head;
if
(firstNode)
{

head = firstNode->next;
delete
firstNode;
}
}

break
;
case
'6':
{

Node* endNode = head;
if
(endNode) //Atleast one element
{
Node* endEndNode = endNode->next;
if
(endEndNode) //Atleast 2 elements
{
while
(endEndNode->next)
{

endNode = endEndNode;
endEndNode = endEndNode->next;
}

endNode->next = NULL;
delete
endEndNode;
}

else
//Only one element
{
head = NULL;
delete
endNode;
}
}
}

break
;
case
'7':
{

Node* tempNode = head;
if
(tempNode)
{

unsigned
num;
cout<<"\tRemove after how many nodes? : ";
cin>>num;

unsigned
count = 1;
//If less elements are present then return
while(tempNode->next && (count < num))
{

tempNode = tempNode->next;
count++;
}

if
(count == num && tempNode->next && tempNode->next->next)
{

Node* nodeToRemove = tempNode->next;
tempNode->next = nodeToRemove->next;
delete
nodeToRemove;
}
}

else

{

cout<<"\tNo nodes present yet"<<endl;
}
}

break
;
default
:
cout<<"Incorrect selection."<<endl;
}
}


return
0;
}



The output is as follows:
You can try more combinations and if you have ideas for improvements please add in the comments section.

Few things to note:
1. This program is for reference and I have not accounted for memory leaks after pressing '0'.
2. For simplicity, getNewNode() is shown as a seperate function. In a real program, it may be better as a method of class Node
3. General Linked Lists use Struct's but in C++, Structs and Classes are nearly the same so its better to use Class.
4. In C++ there is rarely a need to use Linked Lists. Its better to use the STL which already have vectors, stacks, lists, etc.
5. There should be check for memory allocation and try catch blocks that have been ignored for simplicity

Introduction to Linked Lists III

In the article Introduction
to Linked Lists
, we introduced the concept of linked list, the example
program was programmed to be able to add and display the elements in the linked
list. In reality only addition of elements to the linked list is not enough
to take the most out of linked list; we should be able to do other operations
such as insertion, deletion of elements etc.


This article would teach you to do such operation (insertion, addition, deletion
etc).


The program itself is quite big and has enough comments so I won’t discuss
anything here; rather I leave it up to you to understand all the operations
yourself!


  // -- Linked Lists --
// ------------------
// Example program to illustrate
// addition, insertion, deletion
// and display of nodes in the
// linked list

#include<iostream.h>

// node class, this will
// represent the nodes or elements
// of the linked list
class node
{
public:
int info;
node *link;
};

// declare global objects
node *start=NULL;

// function prototypes
void insert(int, int);
void add(int);
void display(void);
void del(int);
void free();

void main(void)
{
int ch,pos,num;

while(ch!=5)
{
cout<<"1> Add";
cout<<"\n2> Insert";
cout<<"\n3> Delete";
cout<<"\n4> Display";
cout<<"\n5> Quit\n";

cin>>ch;

switch(ch)
{
case 1:
cout<<"enter element:";
cin>>num;

add(num);
break;

case 2:
cout<<"enter pos:";
cin>>pos;
cout<<"enter element:";
cin>>num;
insert(pos,num);
break;

case 3:
cout<<"enter element to be deleted:";
cin>>num;
del(num);
break;

case 4:
display();
break;
}
}

// free-up the allocated
// memory
free();
}

// --FUNCTION--
// this function takes two
// arguments, 'loc' is the
// number of elements after
// which the new element having
// value 'inf' has to be inserted
void insert(int loc,int inf)
{
node *temp;
node *temp_new;
int i;

// if invalid, return
if(loc<=0) return;

temp=start;

// skip to the desired
// location where the node
// is to be added
for(i=1;i<loc;i++)
{
temp=temp->link;
if(temp==NULL)
{
cout<<"NOT POSSIBLE!";
return;
}
}

// allocate new node
temp_new=new node;
temp_new->info=inf;
// make it point to the
// respective node
temp_new->link=temp->link;
// make the prev. node where
// the new node is added, to
// point at the new node
temp->link=temp_new;
}

  // --FUNCTION--
// display all the data
// in the linked list
void display(void)
{
node *temp;
temp=start;

// traverse or process
// through each element
// and keep printing
// the information
cout<<"\nelements are...\n";
while(temp!=NULL)
{
cout<<temp->info<<endl;
temp=temp->link;
}
}

// --FUNCTION--
// adds node to the end
// of the linked list
void add(int inf)
{
node *temp1;
node *temp2;

// if the element to be added
// is the first element
if(start==NULL)
{
// allocate a new node
temp1=new node;
temp1->info=inf;
temp1->link=NULL;

// make start point at it
start=temp1;
}
// if not
else
{
temp1=start;

// find out the last element
while(temp1->link!=NULL)
temp1=temp1->link;

// allocate new node
temp2=new node;
temp2->info=inf;
temp2->link=NULL;

// make the last element
// of the list to point
// at the newly created node
temp1->link=temp2;
}
}

// --FUNCTION--
// takes the argument of the
// 'info' part of the node
// to be deleted
void del(int inf)
{
node *temp, *old;

temp=start;

// while list not empty
while(temp!=NULL)
{
// if match is found
if(temp->info==inf)
{
// if it is the
// first node
if(temp==start)
start=temp->link;

else
old->link=temp->link;

delete temp;
return;
}
else
{
// traverse through
// each node
old=temp;
temp=temp->link;
}
}
}

// --FUNCTION--
// free up the allocated memory
// used by the nodes of the
// linked list
void free()
{
// below is a bit confusing
// part.
// here all the nodes that
// we have allocated are
// being freed up
node temp;
while(start!=NULL)
{
// store the next node
// to the one being deleted
temp=*start;

// delete the node
delete start;

// retrieve the next node
// to be deleted
start=temp.link;
}
}

Good-Bye!


Related Articles:


Introduction to Linked Queues

In one of the article Introduction
to Linked Stacks
, I said that representing data structures such as
Stacks and Queues as arrays had one major problem that it can’t have more
than a predefined number of elements. To overcome this we used linked lists
to represent stacks. In this article we’ll use linked lists to represent
queues.


Below are some graphics that illustrate the addition and retrieval of elements
to and from the linked queue.



Addition of elements in the linked queue


FIG.: Addition of data to the linked queue




FIG.: Retrieval of elements from the linked
queue




I don’t think there is anything more that needs to be discussed, so let’s
have a look at the example program:


  // -- Linked Queues --
// C++ Example Program to
// illustrate the representation
// of queues as linked lists
#include<iostream.h>

// node class, this will
// represent the nodes or elements
// of the linked queues
class node
{
public:
int info;
node *link;
};

// declare global objects
node *front=NULL;
node *rear=NULL;

// function prototypes
void add(int);
int retrieve();
void free();

void main(void)
{
int ch=0,num;

while(ch!=3)
{
cout<<"1> Add";
cout<<"\n2> Retrieve";
cout<<"\n3> Quit\n";

cin>>ch;

switch(ch)
{
case 1:
cout<<"enter element:";
cin>>num;

add(num);
break;

case 2:
cout<<"\n\Retrieved: ";
cout<<retrieve();
cout<<"\n\n";
break;
}
}

// free up the memory
free();
}

// function to add new nodes
// to the linked queue
void add(int inf)
{
node *temp;

temp=new node;

temp->info=inf;
temp->link=NULL;

if(front==NULL)
{
rear=front=temp;
return;
}

rear->link=temp;
rear=rear->link;
}

// function to retrieve
// data from the linked
// queue
int retrieve()
{
node *temp;
int inf;

if(front==NULL)
{
cout<<"Queue Empty!\n";
return NULL;
}

inf=front->info;
temp=front;
front=front->link;

delete temp;
return inf;
}

// free the dynamic memory
// allocated in the form of
// nodes of the linked queue
void free(void)
{
// below is a bit confusing
// part.
// here all the nodes that
// we have allocated are
// being freed up
node temp;
while(front!=NULL)
{
// store the next node
// to the one being deleted
temp=*front;
// delete the node
delete front;

// retrieve the next node
// to be deleted
front=temp.link;
}
}

Good-Bye!


Related Articles:


Introduction to Linked Stacks

In the article Data
Structures: Introduction to Stacks
, we saw that there was one major
disadvantage of representing stacks using arrays- the stack like the array could
have a limited number of elements, while stacks should be able to grow up to
any number of elements. Besides this there were other disadvantages too.


In one of the other article about Linked
Lists
, we noticed one useful property of linked lists that they can
grow up to any size to accommodate for the addition of elements and it efficiently
uses the memory too.


So if we combine both of this to from a linked version of the stack then it
won’t have the shortcomings that the array version had.


This is what this article is all about.


pushing and popping


As you know that addition of elements to the stack is known as pushing while
retrieval is known as popping.


The process of pushing and popping in case of linked version of stack is slightly
different from the array version. The following graphics will clear it though!


pushing of elements in the linked stack


FIG: pushing of elements in the linked stack





popping of the elements from the linked stack


FIG: popping of the elements from the linked
stack





Now that you know how the basic operations are performed on linked stacks I
present you with the example program to illustrate this.


As always I would strongly recommend you to read the comments!


  // -- Linked stacks --
// Example program to
// illustrate basic
// push and pop to a
// linked stack
#include<iostream.h>

// node class, this will
// represent the nodes or elements
// of the linked stacks
class node
{
public:
int info;
node *link;
};

// declare global objects
node *start=NULL;

// function prototypes
void push(int);
int pop();

void main(void)
{
int ch=0,num;

while(ch!=3)
{
cout<<"1> Push";
cout<<"\n2> Pop";
cout<<"\n3> Quit\n";

cin>>ch;

switch(ch)
{
case 1:
cout<<"enter element:";
cin>>num;

push(num);
break;

case 2:
cout<<"\n\nPopped: ";
cout<<pop();
cout<<"\n\n";
break;
}
}

// below is a bit confusing
// part.
// here all the nodes that
// we have allocated are
// being freed up
node temp;
while(start!=NULL)
{
// store the next node
// to the one being deleted
temp=*start;
// delete the node
delete start;

// retrieve the next node
// to be deleted
start=temp.link;
}
}

// pushes an element 'inf'
// to the linked stack
void push(int inf)
{
node *temp1;
node temp2;

// if the element to be added
// is the first element of
// linked stack
if(start==NULL)
{
// allocate a new node
temp1=new node;
temp1->info=inf;
temp1->link=NULL;

// make start point at it
start=temp1;
}
// if not
else
{
// store the information
// about the node pointed
// by 'start'
temp2.info=start->info;
temp2.link=start;

temp1=new node;
temp1->info=inf;
// insert the new node
// at the beginning
// and make its link
// point to the prev.
// node pointed by 'start'
temp1->link=temp2.link;

start=temp1;
}
}

// returns an element from the
// linked stack
int pop()
{
node temp;

if(start!=NULL)
{
// store info. about
// the first element
// that has to be pooped
temp=*start;

// delete the node
delete start;
// make start point at the
// next node which had been
// stored
start=temp.link;

return temp.info;
}

return NULL;
}

Good-Bye!


Related Articles:


Introduction to Linked Lists Part II

In the previous article Introduction
to Linked Lists
, we introduced the basic concept of linked list. To
make the program (an the article) as simple as possible, we discussed only the
addition and display of nodes in the linked list although necessary we didn't’t
discussed the deletion of node in that article.


In this article we will be discussing about the deletion of nodes from linked
lists.


Deletion of node (elements) from a linked list


The node to be deleted can be represented by many ways but here we will be
representing it by its info. So if we have the following linked list


Linked lists - Deletion of nodes




And we want to delete node1 then we will express it by its info part (i.e. 10).


The main theory behind deletion of nodes is pretty simple. We need to make
the link pointer of the node before the target node (to be deleted) to point
at the node after the target node. Suppose if we wish to delete node having
info as 10 from the above linked list then it will be accomplished as below:


Linked list - Deletion of nodes


Now since node1 is orphan and has no meaning, it can be deleted
to free-up memory as represented below:


Linked lists - node deleted to free-up memory


The following example program illustrates all this. Keep reading
the comments to understand what is happening where!


  // -- Linked Lists --
// ------------------
// Example program in C++
// to illustrate the most simple
// linked list
// NOTE: this program can do three
// operation [adding, deleting,
// and displaying] of data in a
// linked list
#include<iostream.h>

// node class, this will
// represent the nodes or elements
// of the linked list
class node
{
public:
int info;
node *link;
};

// declare global objects
node *start=NULL;

// function prototypes
void add(int inf);
void display(void);
void del(int);

void main(void)
{
int ch;

// input elements
while(ch!=0)
{
cout<<"enter element to be added:";
cout<<"\nenter 0 to stop...\n";
cin>>ch;

if(ch!=0) add(ch);
cout<<"\n\n";
}

ch=-1;

while(ch!=0)
{
cout<<"enter element to be deleted:";
cout<<"\nenter 0 to stop...\n";
cin>>ch;

if(ch!=0) del(ch);
cout<<"\n\n";
}

cout<<"elements are...\n";
display();

// below is a bit confusing
// part.
// here all the nodes that
// we have allocated are
// being freed up
node temp;
while(start!=NULL)
{
// store the next node
// to the one being deleted
temp=*start;
// delete the node
delete start;

// retrieve the next node
// to be deleted
start=temp.link;
}
}

void add(int inf)
{
node *temp1;
node *temp2;

// if the element to be added
// is the first element
if(start==NULL)
{
// allocate a new node
temp1=new node;
temp1->info=inf;
temp1->link=NULL;

// make start point at it
start=temp1;
}
// if not
else
{
temp1=start;

// find out the last element
while(temp1->link!=NULL)
temp1=temp1->link;

// allocate new node
temp2=new node;
temp2->info=inf;
temp2->link=NULL;

// make the last element
// of the list to point
// at the newly created node
temp1->link=temp2;
}
}

void display(void)
{
node *temp;
temp=start;

// traverse or process
// through each element
// and keep printing
// the information
while(temp!=NULL)
{
cout<<temp->info<<endl;
temp=temp->link;
}
}

// this function takes an
// argument which is the info
// of the node to be delted
void del(int num)
{
node *old;
node *target;

target=start;

while(target!=NULL)
{
// if node to be
// delted is found
if(target->info==num)
{
// if node to be deleted
// is the first node
// in the list
if(target==start)
start=target->link;

// if not
else
// then make the node
// prev. to the node
// to be deleted to
// point at the node
// which is after it
old->link=target->link;

// free-up the memory
delete(target);
return;
}
else
{
// traverse through
// each node
old=target;
target=target->link;
}
}
}

Related Articles:


Introduction to Linked Lists

We have been using arrays to store similar data linearly. While arrays are
simple to understand and easy to implement in common situations, they do suffer
from some drawbacks which are listed below:




  • Arrays have fixed dimensions, even if we dynamically allocate the dimension
    it remains constant throughout. So there is a limit to the number of elements
    it can store.




  • Operations such as insertion and deletion are pretty much difficult to
    implement and increases the overhead because these operations require elements
    in the array to be physically shifted.




Linked lists overcome these drawbacks and are commonly used to store linear
data.


Actually elements of linked lists (called as nodes) store two information,
data and the link (pointer) pointing to the next elements (node).


The elements (nodes) are linked sequentially with the help of link pointers.
So we can say that linked lists are collection of nodes which have data and
are linked sequentially so that all the nodes or elements are grouped together.


In programming sense, linked lists are classes whose general form is:


  class node
{
public:
data-type info;
node *link;
};

Here info stores the actual data while link stores the memory
address of the next node, which forms the link between the nodes.


Graphical Representation of a Node of a Linked List

FIG.: Graphical representation of a node


Following figure illustrates the growing of linked lists, the node which has
its link as NULL is the last element in the linked list.


Growing of linked list

FIG.: Linked lists grows like this


Let us now discuss a bit about how a linked list grows:




  1. We have a pointer that stores the memory address of the first element
    in the linked list, represented as the start pointer (of type node). It
    is NULL to begin with as we don’t have any element in the list.




  2. As an element is added, the start pointer is made to point at it and since
    for now the first element is the last element therefore its link is made
    to be NULL




  3. After the addition of each element the link pointer of the previously last
    element is made to point at new last element. This step continues…




In this way the number of nodes in a linked list can grow or shrink over time
as far as memory permits.


Below is the example program that illustrates linked lists. This program is
made as simple as possible and therefore it only performs the basic action (addition
of element) in the linked list.


  // -- Linked Lists --
// ------------------
// Example program in C++
// to illustrate the most simple
// linked list
// NOTE: It is designed so that it
// could only add nodes to the
// list and display them.
#include<iostream.h>

// node class, this will
// represent the nodes or elements
// of the linked list
class node
{
public:
int info;
node *link;
};

// declare global objects
node *start=NULL;

// function prototypes
void add(int inf);
void display(void);

void main(void)
{
int ch;

// input elements
while(ch!=0)
{
cout<<"enter element to be added:";
cout<<"\nenter 0 to stop...\n";
cin>>ch;

if(ch!=0) add(ch);
cout<<"\n\n";
}

cout<<"elements are...\n";
display();

// below is a bit confusing
// part.
// here all the nodes that
// we have allocated are
// being freed up
node temp;
while(start!=NULL)
{
// store the next node
// to the one being deleted
temp=*start;

// delete the node
delete start;

// retrieve the next node
// to be deleted
start=temp.link;
}
}

void add(int inf)
{
node *temp1;
node *temp2;

// if the element to be added
// is the first element
if(start==NULL)
{
// allocate a new node
temp1=new node;
temp1->info=inf;
temp1->link=NULL;

// make start point at it
start=temp1;
}
// if not
else
{
temp1=start;

// find out the last element
while(temp1->link!=NULL)
temp1=temp1->link;

// allocate new node
temp2=new node;
temp2->info=inf;
temp2->link=NULL;

// make the last element
// of the list to point
// at the newly created node
temp1->link=temp2;
}
}

void display(void)
{
node *temp;
temp=start;

// traverse or process
// through each element
// and keep printing
// the information
while(temp!=NULL)
{
cout<<temp->info<<endl;
temp=temp->link;
}
}

Good-Bye!


Related Articles:


Check out this stream