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

Write an algorithm outputs number of books using psuedocode, A shop sells b...

A shop sells books, maps and magazines. Every item is identified by a unique 4 - digit code. All books have a code starting with a 1, all maps have a code which starts with a 2 and

Infix notation to postfix notation, Which data structure is required to cha...

Which data structure is required to change infix notation to postfix notation?    Stack function is used to change infix notation to postfix notatio n

Splaying steps - splay trees, Readjusting for tree modification calls for r...

Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position

Define the term ''complexity of an algorithm, Define the term 'complexity o...

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

What are expression trees, What are expression trees?  The leaves of an...

What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to

State the ways to construct container taxonomy, State the ways to construct...

State the ways to construct container taxonomy There are several ways that we could construct our container taxonomy from here; one way that works well is to make a fundamental

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Convert a binary tree into its mirror image by traversing it, One can chang...

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.

State the ruby programming language, The Ruby Programming Language Alth...

The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

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