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

Explain dijkstra''s algorithm, Explain Dijkstra's algorithm Dijkstra's ...

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node

Determine relevancy and relative position of two polygons, Comparison Techn...

Comparison Techniques There are several techniques for determining the relevancy and relative position of two polygons. Not all tests may be used with all hidden-surface algori

Heights of 500 students `Algorithms`, Write an algorithm, using a flowchart...

Write an algorithm, using a flowchart, which inputs the heights of all 500 students and outputs the height of the tallest person and the shortest p erson in the school.

Merge sort , What is the best-case number of comparisons performed by merge...

What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

Explain cam software, Explain CAM software CAD/CAM software has been re...

Explain CAM software CAD/CAM software has been recognized as an essential tool in the designing and manufacturing of a product due to its ability to depict the designs and tool

Program segment for deletion of any element from the queue, Program segment...

Program segment for deletion of any element from the queue delete() { int delvalue = 0; if (front == NULL) printf("Queue Empty"); { delvalue = front->value;

Adjacency matrix of an undirected graph, 1) What will call a graph that hav...

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

Various passes of bubble sort, Q. Show the various passes of bubble sort on...

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

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