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

Single pointer pointing to the tail of the queue, Can a Queue be shown by c...

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

Mcs-021, #questWrite an algorithm for multiplication of two sparse matrices...

#questWrite an algorithm for multiplication of two sparse matrices using Linked Lists.ion..

Define an array, Define an array. Array is made up of same data structu...

Define an array. Array is made up of same data structure that exists in any language. Array is set of same data types. Array is the collection of same elements. These same elem

Non-recursive implementation of preorder traversal, For preorder traversal,...

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

Adjacency matrix representation of a graph, An adjacency matrix representat...

An adjacency matrix representation of a graph cannot having information of : Parallel edges

Explain floyds algorithm, Explain Floyd's algorithm It is convenient to...

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an

Define a tree and list its properties, QUESTION (a) Define a tree and l...

QUESTION (a) Define a tree and list its properties. (b) By showing all your workings, draw the spanning tree for the following graph based on the Breadth-First-Search algori

What is Oscillating Sort?, For the Oscillating sort to be applied, it is ne...

For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the po

Boar corloring, Board coloring , C/C++ Programming

Board coloring , C/C++ Programming

State the painter algorithm, Painter's Algorithm As the name suggests, ...

Painter's Algorithm As the name suggests, the algorithm follows the standard practice of a painter, who  would paint the background (such as a backdrop) first, then the major d

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