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

#title., Ask quapplication of data structure estion #Minimum 100 words acce...

Ask quapplication of data structure estion #Minimum 100 words accepted#

What are the dynamic arrays, What are the Dynamic arrays Dynamic arrays...

What are the Dynamic arrays Dynamic arrays are convenient for programmers since they can never be too small-whenever more space is needed in a dynamic array, it can simply be e

Algorithm, give me algorithm of simple interest

give me algorithm of simple interest

Determine the critical path and the expected completion, The information in...

The information in the table below is available for a large fund-raising project. a. Determine the critical path and the expected completion time of the project. b. Plot the total

Reverse order of elements on a slack, Q. Reverse the order of the elements ...

Q. Reverse the order of the elements on a stack S    (i) by using two additional stacks (ii) by using one additional queue. Ans :      L e t S be the stac

Entity relationship diagram, This question is based on the requirements of ...

This question is based on the requirements of a system to record band bookings at gigs. (A 'gig' is an event at which one or more bands are booked to play). You do not need to know

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Cohen sutherland algorithm, Using the cohen sutherland. Algorithm. Find the...

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

Avl tree, Example: (Single rotation into AVL tree, while a new node is inse...

Example: (Single rotation into AVL tree, while a new node is inserted into the AVL tree (LL Rotation)) Figure: LL Rotation The rectangles marked A, B & C are trees

Sparse matrix, memory address of any element of lower left triangular spars...

memory address of any element of lower left triangular sparse matrix

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