Single Linked List

queue model :
the queue adt stores arbitrary objects . insertions and deletions follow the first-in first-out scheme .insertions are at the rear of the queue and removals are at the front of the queue.

main queue operations:
- enqueue(object): inserts an element at the end of the queue
-object dequeue(): removes and returns the element at the front of the queue.

auxiliary queue operations:
-object front(): returns the element at the front without removing it.
-integer size(): returns the number of elements stored .
-boolean isempty(): indicates whether no elements are stored .


array-based queue
use an array of size n in a circular fashion .two variables keep track of the front and rear.
f index of the front element
r index immediately past the rear
element

array location r is kept empty


queue operations:
we use the modulo operator (remainder of division)

size()
return (n ? f + r) mod n

isempty()
return (f == r)

enqueue(x)
if size() = n ? 1 then
write ( queue is full )
else
q[r] ? x
r ? (r + 1) mod n



dequeue()
if isempty() then
write( queue is empty )
else
x ? q[f]
f ? (f + 1) mod n
return x

queue :
stores a set of elements in a particular order .
-insertions and deletions follow the first-in first-out scheme
-insertions are at the rear of the queue and removals are at the front of the queue


main queue operations
en_queue(o)
insert the object o at rear of the queue
insert(x):
a[rear] ? x
rear ?(rear+1) mod n
dequeue()
remove object from front of queue
remove():
x ? a[front]
front ?(front) mod n
return x
size( ): number of elements

isempty( ): size == 0?

front( ): look at object at front of queue



array-based queue implementation
- array of fixed size
- index array element for front and rear of queue
-indices “wrap around” when they cross end of array





single linked lists
the linked list consists of a series of structures called nodes. each node contains two fields: a "data" field and a "next" field which is a pointer used to link one node to the next node.
each node is allocated in the heap with a call to malloc(), so the node memory continues to exist until it is explicitly deallocated with a call to free().the node called a head is the first nod in the list . the last node s next pointer points to null value. the following figure shows the actual representation of the list with its deleting and insert operations .




















programming details
before writing the code to build the above list, we need two data types:
• node the type for the nodes which will make up the body of the
list. these are allocated in the heap. each node contains a single
data element and a pointer to the next node in the list.


struct node
{
int data
struct node* next
}


• node pointer the type for pointers to nodes.
struct node
{
int data
struct node *next
}
typedef struct node* list
list header
here is simple function which uses pointer operations to build the list {1, 2, 3} :

struct node* buildonetwothree() //example1
{
node* head = null
node* second = null
node* third = null
head = (node*)malloc(sizeof(struct node))
second =(node*) malloc(sizeof(struct node))
third = (node*)malloc(sizeof(struct node))
head-> data = 1
head-> next = second
second-> data = 2
second-> next = third
third-> data = 3
third-> next = null
return head
}
from this code, we get a linked list likes




length() function:
the length() function takes a linked list and computes the number of elements in the list.
int length(node* head) // example1
{
node* current = head
int count = 0
while (current != null)
{ count++
current = current-> next
}
return count
}
calling length()
here s some typical code which calls length().
struct node* mylist = buildonetwothree()
int len = length(mylist) // results in len == 3
buildonetwothree() cotains three steps to add a node in the list:
1- allocate the new node in the heap and set its data .
struct node* newnode
newnode = malloc(sizeof(node))
newnode-> data = data
2- link next set the .next pointer of the new node to point to the current first node of the list.
newnode-> next = head
3- link head change the head pointer to point to the new node, so it is now the first node in the list.
head = newnode

iterate down a list
a very frequent technique in linked list code is to iterate a pointer over all the nodes in a list .to do so we need to
1- the head pointer is copied into a local variable current which then
iterates down the list.
2-test for the end of the list with current!=null.
3- advance the pointer with current=current-> next
the three steps are accomplished by this code
for (current=head current!=null current=current-> next)

changing a pointer with a reference pointer
many list functions need to change the caller s head pointer. to do this in the c language, pass a pointer to the head pointer . the main steps for this technique are...
• design the function to take a pointer to the head pointer. this needs to change a struct node*, to a struct node**.
• use & in the caller to compute and pass a pointer to the value of
interest.
• use * on the parameter in the called function to access and change the
value of interest


linked list has of several functions like :
appendnode_last() and appendnode_first() functions:
appendnode_last() adds the new node at the tail end of the list. if the list is empty, it uses the reference pointer to change the head pointer. otherwise it uses a loop to locate the last node in the list. appendnode_first() adds the new node at the head of the list.


void appendnode_last(list *head,int value)
{ list temp,nod
nod=(node*)malloc(sizeof(node))
nod-> data=value
nod-> next=null
if(*head==null)
*head=nod
else
{
for(temp=*head temp-> next!=null temp=temp-> next)
temp-> next=nod
}
}
void appendnode_first(list *head,int value)
{
list nod
nod=(node*)malloc(sizeof(node))
nod-> data=value
nod-> next=*head
*head=nod
}

calling appendnode_last() and appendnode_first() functions
appendnode_first(&head,11)
appendnode_last(&head,99)

copylist() function
it takes a list and returns a complete copy of that list.
node* copy_list(node* head1)
{ node *head2,*temp1,*temp2
if(head1==null)
{
head2=null
return head2
}
temp1=head1
head2=(node*)malloc(sizeof(node))
temp2=head2
while(temp1-> next)
{
temp2-> data=temp1-> data
temp2-> next=(node*)malloc(sizeof(node))
temp1=temp1-> next
temp2=temp2-> next
}
temp2-> data=temp1-> data
temp2-> next=null
return head2
}


copylist() recursive
// recursive variant
node* copy_list_rec(node* head1)
{
if(!head1)
return null
node* newnode=(node*)malloc(sizeof(node))
newnode-> data=head1-> data
newnode-> next=copy_list_rec(head1-> next)
return newnode
}

calling copylist() function
list head1=copy_list_rec(head)
deletinglast node() and deletingfirstnode() functions:
deletinglast node() deletings the node from the tail end of the list. it uses the reference pointer to change the head pointer. otherwise it uses a loop to locate the last node in the list.
deletingfirstnode() deletings the node from the head of the list
del_node(int index) deletings the node that has the order index in the list.
void del_lastnode(list* head)
{
node* temp,*prev
if(*head==null) return
temp=*head
prev=null
while(temp-> next!=null)
{
prev=temp
temp=temp-> next
}
if(prev==null)
*head=null
else
prev-> next=null
free(temp)
}
void delfirstnode(list* head)
{ //example1
list temp
if(*head!=null)
{
temp=*head
*head=(*head)-> next
free(temp)
}
}
void del_node(list* head,int index)
{ //example1
list temp , prev
int count=1
if(*head==null || index< 1) return
prev=null
temp=*head
while(temp!=null && count< index)
{ prev=temp
temp=temp-> next
count++
}
if (temp==null ) return
if (prev==null)
*head=temp-> next
else
prev-> next=temp-> next
free(temp)
}

displist():display the contents of the list.
void displist(node* head)
{
list temp
cout< < "\n\n\t\t\t list \n\n"
for(temp=head temp!=null temp=temp-> next)
cout < < temp-> data< < \n
}