link lists

dynamic memory allocation
dynamic memory allocation means to access memory randomly. in arrays we got series of memory locations. but the drawback of the array is that it has a fixed size. and it will take that fixed memory even if you don’t use all the locations. from here the concept of dynamic memory arises. so we get different locations in memory and then link them. we can achieve this by linked list.

linked list
linked list is a dynamic data structure. in linked list we have a structure called node. the structure has 2 parts one part is called data and other is called link. link is used to tie new node. a linked list must have a start pointing to first node. think of link list as a train with start as an engine of the train. so here is a linked list.
data next

data next

data next






this linked list has three nodes in it, each with a link to the next node in the series. the last node has a link to the special value null, to show that it is the last link in the list. there is also another special pointer called start, which points to the first link in the list so that we can keep track of it.


here is a code how to create node in c++ :
struct node
{ int data
node *next
}
node *start
in this structure we have created a node with one data member and one link.
here is simple program to build link list and display:
#include
#include
struct node
{int data
node *next
}
node *start=null
node *n node *t node *cur node *d
void creat_link(int value)
{ if(start==null)
{start=new node
start->data=value
start->next=null
n=start t=start cur=start
}
else
{ n= new node
n->next=t->next
t->next= n t=n
n->data=value }}
void main()
{ clrscr()
for(int i=1 i<=5 i++)
{ cout<<"enter value"
cin>> value
creat_link(value)
}
while(cur != null) // print or display link list
{ cout<data
cur=cur->next
}}
functions on linked list
there are some functions can be done on linked list. here we describe some of it.
insertion and deletion functions
a list is a dynamic data structure. the number of nodes on a list may vary as elements are inserted and deletingd. there are several types of insertion and deletion functions can done on linked lists. there are: (insert first, insert last, insert in any location, deleting first, deleting last and deleting from any location).
insertion at last
to insert new element to the list we need to create new node with the new pointer called p. we can t move the start pointer because the list will be lost. instead, we need to a temporary pointer called temp have value equal to start pointer value. then move temp pointer to the end list until temp-> next = null then add the new node p. desire to add the integer 6 to the front of that list . the next figure show the steps of adding a new item to the list.


1. consider we have the following linked list:
5 next

3 next

8 next





6 next


2. use a temporary pointer temp initialized on head pointer :
5 next

3 next

8 next





3. move the temp pointer until temp - > next = null:
5 next

3 next

8 next





4. linked the pointer of temp to the new node p:
5 next

3 next

8 next

6 next



on the following c++ code of insertion node at last of the linked list:
void addlast ()
{ node * p
p= new node
p->data=6
p->next=null
if(start==null)
start=p
else
{node *temp=start
while(temp->next!=null)
temp=temp->next
temp->next=p
}
}



deleting first node
5 next

3 next

8 next







void deleting_first_node()
{ node * p
if(start==null)
cout<<"error"
else
{ p=start
start=p->next
p->next=null
deleting p
}
}


insertion at first
the new element will added to the beginning of linked list, therefore , there is no need to using a temporary pointer. the code will be:
5 next

3 next

8 next




6 next



void addfirst()
{ node * p
p= new node p->data=6
if(start==null)
{ start=p
p->next=null
}
else
{p->next=start start=p
}
}
deletion from last
for deleting node from last we need to two temporary pointers moved to the end of the list and then deleting the last node as following :
5 next

3 next

8 next




void deleting_last_node()
{ node * p
if(start==null)
cout<<"error"
else
{ p=start
while(p->next != null)
{ q=p
p=p->next
}
}
}

compute the length of list
implement function computes the number of nodes in the list:
int length()
{ node * p
int count=0
if(start==null)
cout<<"the no. of list zero"
else
{ p=start
while( p!= null )
{count=count+1
p=p->next
}
}
return count
}





insertion at any location
implement function add node at any location for link list:
void add_node_at_any location()
{ node * p node *temp
p=new node
p->data=40
temp=start
if(start==null)
cout<<"error"
else
{ for(int i=1 i temp=temp->next
p->next=temp->next
temp->next=p
}
}



deletion at any location
implement function deleting node at any location for link list:
void del_node_at_any location()
{ node * p node *temp
temp=start
if(start==null)
cout<<"error"
else
{ for(int i=1 i temp=temp->next
p=temp->next
temp->next=p->next
p->next=null
deleting p
}
}




inverse link list
implement function to inverse link list:
void inverse()
{ node * p node *curr node *prev
prev=null
curr=start
if(start==null)
cout<<"error"
else
{ while(curr != null)
{p=curr->next
curr->next=prev
prev=curr
curr=p
}
start=prev
}
}

implement stack by using link list
void push(int x)
{ temp=new node
temp->data=x
temp->next=top
top=temp }
void pop()
{temp=top
top=top->next
temp->next=null
deleting temp
}

exercise: implement simple queue by using link list .
questions:
q1:write a count() function that counts the number of nodes that have negative value in a link list.
q2: write a getnth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position .
q3-write a sortedinsert() function which given a list that is sorted in increasing order.
q4-write an append() function that takes two lists, a and b , appends b onto the end of a .
q5-given a list, split it into two sublists — one for the front half, and one for the back half. if the number of elements is odd, the extra element should go in the front list. so frontbacksplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7,11}.
q6- write a movenode() function that takes two lists, removes the front node from the second list and pushes it onto the front of the first.