Doubly linked lists-implementation, Data Structure & Algorithms

Assignment Help:

In any singly linked list, each of the elements contains a pointer to the next element. We have illustrated this before. In single linked list, traversing is probable only in one direction. Sometimes, we ought to traverse the list in both of the directions to improve performance of algorithms. To enable this, we require links in both the directions, i.e., the element has to have pointers to the right element in addition toto its left element. This type of list is called  asdoubly linked list.

141_DOUBLY LINKED LISTS-IMPLEMENTATION.png

Figure: A Doubly Linked List

Doubly linked list is described as a collection of elements, each of element consisting of three fields:

Ø  pointer to left element,

Ø  data field, &

Ø  pointer to right element.

Left link of the leftmost element is set to NULL that means that there is no left element to that. And, right link of the rightmost element is set to NULL that means that there is no right element to that.

ALGORITHM  (Creation)

Step 1                begin

Step 2                define a structure ELEMENT with  fields

Data

Left pointer

Right pointer

Step 3                declare any pointer by name head and using (malloc()) memory allocation  function  allocate  space  for  one  element  &  store  the address in head pointer

Head = (ELEMENT *) malloc(sizeof(ELEMENT))

Step 4                read the value for head->data head->left = NULL

head->right = (ELEMENT *) malloc(size of (ELEMENT))

Step 5                repeat step3 to create needed number of elements

Step 6                end

 

Program demonstrated the creation of a Doubly linked list.

/* CREATION OF A DOUBLY LINKED LIST */

/* DBLINK.C */

# include

# include

structdl_list

{

int data;

structdl_list *right;

structdl_list *left;

};

typedefstructdl_listdlist;

voiddl_create (dlist *);

void traverse (dlist *);

/* Function creates simple doubly linked list */

voiddl_create(dlist *start)

{

printf("\n Insert values of element -1111 to come out : ");

scanf("%d", &start->data);

if(start->data != -1111)

{

start->right = (dlist *) malloc(sizeof(dlist));

start->right->left = start;

start->right->right = NULL;

dl_create(start->right);

}

else

start->right = NULL;

}

/* Display the list */

void traverse (dlist *start)

{

printf("\n traversethe list usingright pointer\n");

do {

printf(" %d = ", start->data);

start = start->right;

}

while (start->right); /* Demonstrates value of last start only one time */

printf("\n traversethe listusing left pointer\n");

start=start->left;

do

{

printf(" %d =", start->data);

start = start->left;

}

while(start->right);

}

{

dlist *head;

head = (dlist *) malloc(sizeof(dlist));

head->left=NULL; head->right=NULL; dl_create(head);

printf("\n created doubly linked list is as ");

traverse(head);

}


Related Discussions:- Doubly linked lists-implementation

Perform depth -first search, You are given two jugs, a 4-gallon one and a 3...

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Tower of hanoi, how do we use 4-discs stack to solve tower of hanoi problem...

how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?

Array, extra key inserted at end of array is called

extra key inserted at end of array is called

frequenty count of function, Ask question find frequency count of function...

Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Header linked list, creation,insertion,deletion of header linked list using...

creation,insertion,deletion of header linked list using c.

Queues, what is queues? how it work? and why it used? i want an assignment...

what is queues? how it work? and why it used? i want an assignment on queue .....

Explain in detail about the abstract data type, Abstract data type The ...

Abstract data type The thing which makes an abstract data type abstract is that its carrier set and its operations are mathematical entities, like geometric objects or numbers;

Example of binary search, Let us assume a file of 5 records that means n = ...

Let us assume a file of 5 records that means n = 5 And k is a sorted array of keys of those 5 records. Let key = 55, low = 0, high = 4 Iteration 1: mid = (0+4)/2 = 2

Recursion, differences between direct and indirect recursion

differences between direct and indirect recursion

List various problem solving techniques, List various problem solving techn...

List various problem solving techniques. There are two techniques:- 1.  Top down 2.  Bottom- up

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd