|
Arrays can be used to store a series of
data when the members of the series is fixed or bounded. But if the length
of array is to be decided in the run time, Linked list can be used. This
article helps you to start programming with linked lists.
Why Linked lists?
Let us
consider an example of implementation of a STACK or a QUEUE using a linear
array then it is necessary to declare the SIZE of the STACK or QUEUE array
(at Compile time) this may leads to either memory wastage or insufficient
memory. This is the main disadvantage of a linear array. So if we use a
linked list, we can allocate the memory "Dynamically" ( ie. during Run
time). So there will not be any problem of memory wastage or insufficient
memory.
Whenever we
want to insert or delete an element from a linear array either we must
overwrite the value or we should shift the elements to new location. Where
as in a linked list we can directly insert or delete the elements without
effecting the other elements.
In
the conventional linear array storage the memory allocation is contiguous.
for ex: When we declare an integer array in 'C /C++ language'
int
a[100]; //array declaration int is the data type size is 4
then '&a[0]' or &a is
called as the base address .If we want to access the element through direct
addressing then a[1] will be located at a location (&a[0]+ size(int)). Here
size of int data type is 2 bytes. The addresses of the element located
in an array at a position ' k' can be calculated using the formula given
below
LOC (Array [k])= Base Address
(Array) + k * size( data type declared)
'k' is the index of
element . If the base address(&a[0]) is 1000, and data type is integer then
next element will be located at the location 1002 (i.e.&a[1]= 1000+ 1*(2)),
similarly the address of the element a[4] is 1008. So whenever we access
the data, the computer calculates the address location as mentioned above .
This process is much slower when compared to directly fetching data form
memory using a pointer.
In A
linked list ach NODES don't need to be located in adjacent location. The
storage may not be contiguous in a linked list. In a linked list , the
access of data is done using a pointer. Thus the data access is much faster
in linked list.
A linked list have an extra
field to store the link address .
What is a linked list?
A linked list
is a linear data structure used to organize the data in the memory. As its
name indicates linked list is a list of items called the 'NODE' linked
using pointers. A 'NODE' is a structure of List containing two or more
fields called the 'data /Info' field and 'Link/address' field. A linked list
can be of any of the following type.
 Singly-Linked
Lists
Doubly-Linked
Lists or Two way Linked List
Circularly-Linked
Lists
Circularly-Doubly
Linked Lists
NODE: A node is user
defined structure. A node has at least two fields data field and link
field. Here the following figure shows a node.
NODE
It is not necessary that a
node should have two fields we may have more than one data field.
|
 ........
|
here
data1,data2,...data n are the data fields. The data field may contain
Integer data or string data or a character data.
LINK field is a
pointer contains the address of the node related to it. A link is denoted by
a arrow symbol as shown below
Every Node will have an
address. Here 1000 is the address of the second node. So the link field of
the previous node (first node) to it contains the value 1000
The general structure of a NODE is
given as
struct tag_name {
type member1;
type member2;
......................
......................
.....................
struct tag_name *linknext; //pointer stores the address of next node
}
In the above given structure
member1,member2,...etc are the data fields of node. These member variables
need not be of the same data type
example:
struct Node {
//Node is the tag name given here
int rollno; //this is of integer type
char name[20]; //this is of char type
......................
......................
.....................
struct Node *link; //stores the address of next node
}
Now let us see what is a Singly Linked List :
The following figure shows a
singly linked list. It has single link field extended as list
The above picture shows a
singly linked list the first node is called the header node . This is the
entry point to the list and the list is terminated when the link field of
any of the node is NULL.
Now let us see what is a Doubly-Linked List :
The following figure shows
a doubly linked list . The link is two way. Here the NODE contains two
pointers LPTR left pointer and the RPTR right pointer. LPTR points to the
previous node and RPTR points to the next node. Please note that whenever
there is no node to point then the link is poited to NULL.
The advantage of Two way
linked list is that the traversal becomes easy.
Now let us see what is a Circularly-Linked List :
A Circularly linked list is similar to
singly linked list except that the " 'Link' field of Last NODE
points to the first node"
Now we shall see the class
implementation of a linked list:-
//Implementation of a linked list
#include<iostream.h>
#include<conio.h>
class linklist{
private:
struct node{
int data;
node *link;
}*p;
public:
linklist();
void addend(int num);
void addbeg(int num);
void addafter(int c,int num);
void del(int num);
void display();
int count();
~linklist();
}; |
|
//add a new node at the
beginning of the linked list
void linklist::addbeg(int num)
{
node *q;
//add newnode
q=new node;
q->data=num;
q->link=p;
p=q;
}
|
the above function adds a new node
at the beginning
What are the
operations that can be performed on Singly-Linked list ?
The operations that can be
performed on a linked list are
Insertion
of a new node to the beginning of a list, end of a list, or inserting In-
between two nodes new node at the end of the linked list
// add a node
at a specified location in the list
void linklist::addafter(int c,int num)
{
node *q,*t;
int i;
q=p;
for (i=0;i < c;i++)
{
q=q->link;
if(q==NULL)
{
cout<<"there is no such node existing:"<<endl;
return;
}
}
t=new node;
t->data=num;
t->link=q->link;
q->link=t;
} |
the above function adds a node at a
specified location
|
//
insert at the end
void
linklist::addend(int num)
{
node *q,*t;
//if the list is empty
if(p==NULL)
{
p=new node;
p->data=num;
p->link=NULL;
}
else
{
q=p;
while(q->link!=NULL)
q=q->link;
t=new node;
t->data=num;
t->link=NULL;
q->link=t;
}
}
|
The above function adds a node
at the end of list
Deletion
of a node:
|
//deletes the specified
node from the linked list
void linklist:: del(int num)
{
node *q,*r;
q=p;
//if node to be deleted is the first node
if (q->data==num)
{
p=p->link;
delete q;
return;
}
r=q;
while(q!=NULL)
{
if(q->data==num)
{
r->link=q->link;
delete q;
return;
}
r=q;
q=q->link;
}
}
|
Traversing
a node and displaying data:
|
void
linklist::display()
{
node *q;
clrscr();
cout<<endl;
for(q=p;q!=NULL;q=q->link)
cout<<"
"<<q->data;
}
|
Here is the main program ;
|
//This is the main program
void main()
{
linklist list;
cout<<endl;
list.addbeg(11);
list.addbeg(834);
list.addbeg(187);
list.addbeg(7);
list.addbeg(1);
list.addend(1 );
list.addafter(0,330);
list.display();
getch();
}
|
|
