Double Linked List

Doubly linked list (or) Double linked list :-

Double Linked list is a fundamental data structure used in computer programming. It consists of a sequence of nodes connected by two pointers in both directions. Each node is having three parts the first part contains the address of previous node and second part contains data and third part contains address of next node. The first and third part is called address fields and the second part is data field. The start pointer always points to the first node of a list. The graphical representation of a node structure shown in the fig

From the above fig the node is containing 2 pointers.

1. Pointer1 is pointing to the previous node.

2. Pointer2 is pointing to the next node.

Doubly linked list can be represented as above fig. in doubly linked list it is possible to traverse both forward & backward directions. It is also called two way lists.

Operation applied on double linked list:

· Inserting an element

· Delete element from the list

· Find the length of the list

· Read the list from left to right or right to left

· Copy a list

· Sort the elements in either ascending or descending order

· Combine 2 or more list

· Search a list

Algorithm to add an element to an existing list:

It is possible to add element to an existing list in thee ways they are add at the front, add at the end of the list, add after a node of the existing list.

Assumtion start always contains the current list start node address.

>next stands for next node address

Add node at the front of a list

Step1. Create a new node

Step2. n->right = start

Step3. start->left = n

Step4. start = n

dd node at the end of a list

Step1. Create a new node

Step2. t = start where t is a temporary variable.

Step3. Traverse the tree until t->right = null

Step4. t->right = n

Step5. n->left = t

Add node after a particular position or a node

Step1. Create a new node.

Step2. t = start where t is a temporary pointer variable

Step3. Read position p from console.

Step4. Traverse the list until the position p

Step5. if not found the position error “no such node exist “: go to step 9

Step6. n->right = p->right

Step7. n->left = p

Step8. p->right = n

Step9. End

Insert node after second (2) node

Single Linked List

Single linked list: -

Single Linked list is a linear data structure. It is used as a fundamental data structure in computer programming. It contains a collection of nodes which are connected by only one pointer in one direction. Each node is having two parts the first part contains the data and second part contains the address of the next node. The first part is called data field or information field and the second part is called as link field or next address field.

The graphical representation of linked list is

Hear the pointer start always points to the first node of a list and the end node is represented by special value called NULL.

Need for linked representation :-

The following problem arises when it is implemented by using arrays

1. Wastage of storage

2. It is not possible to add or delete in the middle of a list with out rearrangement

3. It is not possible to extend the size of a list

To overcome all the above problem by implementing the list using linked representation. In linear lists insertion and deletion operations are inexpensive.

Operations applied on single linked list:

The basic types of operations applied on single linked list are

.

1. Inserting a new element at the given position

2. Delete the element from the given position

3. Find the length of the list

4. Read the list from left to right

5. Retrieve the ith element

6. Copy a list

7. Sort the elements in either ascending or descending order

8. Combine 2 or more list

Algorithm to add an element to an existing list:

It is possible to add an element to an existing list in three ways they are

1) Add at the front

2) Add at end of list

3) Add at position

Assumptions :

1) start is a pointer which always points to the first node of a list

2) ->next stands for next node address

Add at the front of a list

Step1: create a new node

Step2: newnode->next = start

Step3: start = newnode

Add at the end of a list

Step1: create a new node (newnode)

Step2: t = start

Step3: while (t->next != NULL ) t=t->next;

Step3: t->next = newnode

Add after a node of a list (position)

Step1: create a new node (newnode)

Step2: read the position of the node p;

Step3: t = start

Step4: traverse the list up to position as

for (i=1; inext;

Step4: newnode->next = t->next;

Step5: t->next = newnode

Algorithm for delete an element from the list

it is possible to delete an element from an existing list in three ways

· Delete at front

· Delete at end

· Delete at a position

Delete at front:

Step1: t1 = start

Step2: start = start->next

Step3: delete (t1)

Delete at end :

Step1: t = start;

Step2: traverse the list up to n-1 nodes as

For (I =1; I < t =" t-">next

Step3: t1= t->next;

Step4: t->next = t->next->next;

Step5: delete ( t1 )

Delete at position:

Step1: read the position of the deleted node p

Step2: traverse the list upto p-1as

For (i=1;inext;

Step3: t1 = t->next;

Step4: t->next= t->next->next

Step5: delete (t1)


delete a node at position 2

Drawbacks of a single linked list:

It is having only one pointer so that it is possible to traverse in only one way

Linked Lists

Linked list: -

Linked list is a linear data structure that works on a principle Random in Random out (RIRO). Linked list can be defined as Collection of logically adjacent nodes in which logical adjacency is maintained by pointers.

Ex: The days of the week (Sun, Mon, Tue, Wed, Thu, Fri, Sat)

Linked lists can be represented in memory by two ways they are

· Using array method 2. Using pointer method

Array method :

In array method all the elements are stored in the continuous memory locations. It is having following disadvantages they are

1. It follows static memory allocation.

2. It is not possible to extend the size of the array at runtime

3. Due to static memory allocation some memory space will be wasted.

Pointer method :

In pointer method all the data elements are represented using nodes. Each node is having data item and pointer to the next node. The elements in the list need not occupy continuous memory locations. The advantages of this method are

· Efficient memory management is possible, i.e., due to dynamic memory allocation the memory is not wasted

· It is possible to add or delete an element any ware in the list

· It is dynamic in nature

· It is possible to handle a list of any size

· It is possible to extend the size of a list at runtime

Various operations performed on lists: -

The operations performed on lists are.

1. Inserting a new element at the given position.

2. Delete the element from the given position

3. Find the length of the list

4. Read the list from left to right

5. Retrieve the ith element

6. Copy a list

7. Sort the elements in either ascending or descending order

8. Combine 2 or more list

Circular Queue Data Structure

Circular queue :-

In a standard queue data structure rebuffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue

Circular queue is a linear data structure. It follows FIFO principle.

• In circular queue the last node is connected back to the first node to make a circle.
• Circular linked list fallow the First In First Out principle
• Elements are added at the rear end and the elements are deleted at front end of the queue
• Both the front and the rear pointers points to the beginning of the array.
• It is also called as “Ring buffer”.
• Items can inserted and deleted from a queue in O(1) time.

Circular Queue can be created in three ways they are

· Using single linked list

· Using double linked list

· Using arrays

Using single linked list:

It is an extension for the basic single linked list. In circular linked list Instead of storing a Null value in the last node of a single linked list, store the address of the 1st node (root) forms a circular linked list. Using circular linked list it is possible to directly traverse to the first node after reaching the last node.

The following figure shows circular single linked list:

Using double linked list

In double linked list the right side pointer points to the next node address or the address of first node and left side pointer points to the previous node address or the address of last node of a list. Hence the above list is known as circular double linked list.

The following figure shows Circular Double linked list :-

Algorithm for creating circular linked list :-

Step 1) start

Step 2) create anode with the following fields to store information and the address of the next node.

Structure node

begin

int info

pointer to structure node called next

end

Step 3) create a class called clist with the member variables of pointer to structure nodes called root, prev, next and the member functions create ( ) to create the circular linked list and display ( ) to display the circular linked list.

Step 4) create an object called ‘C’ of clist type

Step 5) call C. create ( ) member function

Step 6) call C. display ( ) member function

Step 7) stop

Algorithm for create ( ) function:-

Step 1) allocate the memory for newnode

newnode = new (node )

Step 2) newnode->next=newnode. // circular

Step 3) Repeat the steps from 4 to 5 until choice = ‘n’

Step 4) if (root=NULL)

root = prev=newnode // prev is a running pointer which points last node of a list

else

newnode->next = root

prev->next = newnode

prev = newnode

Step 5) Read the choice

Step 6) return

Algorithm for display ( ) function :-

Step 1) start

Step 2) declare a variable of pointer to structure node called temp, assign root to temp

temp = root

Step 3) display temp->info

Step 4) temp = temp->next

Step 5) repeat the steps 6 until temp = root

Step 6) display temp info

Step 7) temp=temp->next

Step 8) return

Using array

In arrays the range of a subscript is 0 to n-1 where n is the maximum size. To make the array as a circular array by making the subscript 0 as the next address of the subscript n-1 by using the formula subscript = (subscript +1) % maximum size. In circular queue the front and rear pointer are updated by using the above formula.

The following figure shows circular array:

Algorithm for Enqueue operation using array

Step 1. start

Step 2. if (front == (rear+1)%max)

Print error “circular queue overflow “

Step 3. else

{ rear = (rear+1)%max

Q[rear] = element;

If (front == -1 ) f = 0;

}

Step 4. stop

Algorithm for Dequeue operation using array

Step 1. start

Step 2. if ((front == rear) && (rear == -1))

Print error “circular queue underflow “

Step 3. else

{ element = Q[front]

If (front == rear) front=rear = -1

Else

Front = (front + 1) % max

}

Step 4. stop

DeQueue Data Structure

DeQueue (or) Deque (Double ended Queue) :-

DeQueue is a data structure in which elements may be added to or deleted from the front or the rear.

Like an ordinary queue, a double-ended queue is a data structure it supports the following operations: enq_front, enq_back, deq_front, deq_back, and empty. Dequeue can be behave like a queue by using only enq_front and deq_front , and behaves like a stack by using only enq_front and deq_rear. .

The DeQueue is represented as follows.

DeQueue can be represented in two ways they are

1) Input restricted DeQueue 2) output restricted DeQueue

The out put restricted Dequeue allows deletions from only one end and input restricted Dequeue allow insertions at only one end.

The DeQueue can be constructed in two ways they are

2) Using array 2. using linked list

Algorithm to add an element into DeQueue :

Assumptions: pointer f,r and initial values are -1,-1

Q[] is an array

max represent the size of a queue

enq_front

step1. Start

step2. Check the queue is full or not as if (f <>

step3. If false update the pointer f as f= f-1

step4. Insert the element at pointer f as Q[f] = element

step5. Stop

enq_back

step1. Start

step2. Check the queue is full or not as if (r == max-1) if yes queue is full

step3. If false update the pointer r as r= r+1

step4. Insert the element at pointer r as Q[r] = element

step5. Stop

Algorithm to delete an element from the DeQueue

deq_front

step1. Start

step2. Check the queue is empty or not as if (f == r) if yes queue is empty

step3. If false update pointer f as f = f+1 and delete element at position f as element = Q[f]

step4. If ( f== r) reset pointer f and r as f=r=-1

step5. Stop

deq_back

step1. Start

step2. Check the queue is empty or not as if (f == r) if yes queue is empty

step3. If false delete element at position r as element = Q[r]

step4. Update pointer r as r = r-1

step5. If (f == r ) reset pointer f and r as f = r= -1

step6. Stop

Priority Queue

Priority queue :

Priority queue is a linear data structure. It is having a list of items in which each item has associated priority. It works on a principle add an element to the queue with an associated priority and remove the element from the queue that has the highest priority. In general different items may have different priorities. In this queue highest or the lowest priority item are inserted in random order. It is possible to delete an element from a priority queue in order of their priorities starting with the highest priority.

The above figure represents 3 separated Queues each following FIFO behavior. Elements in the 2nd Queue are removed only, when the first Queue is empty and elements from the 3rd Queue are removed only when the 2nd Queue is empty and soon.

Queue Data Structure

Queue Data Structure:

• Queue is a linear data structure
• it works on the principle First In First Out (FIFO).
• The first element insert into the queue is the first element to be delete
• Insertion can be done at rear end using rear pointer and deletions can be done at front end using front pointer
• It looks like open tube.
• The insertion operation is called append/enqueue operation
• The deletion operation is called as serve/dequeue operation.
• Enqueue operation on a full queue causes overflow.
• Dequeue operation on empty queue causes underflow.
• The initial value of the front and rear pointer is always –1
• The pointer front points to the starting end of the queue
• The pointer rear points to the rear end of the queue

For example

The fig 01 illustrates a queue containing three elements a, b and c. the element (a ) is at the front of the queue and c is at the rear of the queue. Fig 02 shows queue after deleting an element. Since elements may be deleted only from the front of the queue, (a) is removed and b is now at the front. Now fig 03 shows queue after inserting elements d and e , they must be inserted at the rear of the queue.

Operations of a queue:

There are two operations applied on queue they are 1 enqueue 2. dequeue. While performing enqueue operation check the queue is Full or not and while performing dequeue operation check the queue is empty or not.

Enqueue:

Insert an element into the queue is called Enqueue operation. Insertion can be done at rear end. At the time of insertion first check the queue is full or not. If the queue is full it generates an error message “queue if Full”.

Dequeue:

Delete an element from the queue is called Dequeue operation. Deletion can be done at front end. At the time of deleting first check the queue is empty or not. If the queue is empty it generates an error message “queue is empty”.

Assumptions:

rear, front are pointers , initial values are -1, -1

max_queue is the size of the queue

Q[ ] is an array

element is the element to be added or deleted

Algorithm for adding an element in to the queue (enqueue):

Step1: start

Step2: if (rear == max_queue - 1) then error “queue is full “go to step 5

Step3: else{ update front as front = front +1

Step4: put the element into the queue at rear as queue [rear] = element }

Step5: stop.

Algorithm for deleting an element from the queue (dequeue):

Step1: start

Step2: if (front == rear) then error “queue is empty” go to step5

Step3: else {update front as front = front +1

Step4: delete an element from front as element = queue [front]}

Step5: stop.

Applications of queue:

· Queues can be used to store the interrupts in the operating system

· It is used by an application program to store the incoming data

· Queue is used to process synchronization in Operating System

· Used for job scheduling

Drawbacks of a queue:

For each and every enqueue operation the queue is to be rearranged other wise even the queue is having an empty space it is not possible to utilize.