Question

Project 6: Create a double-linked list and traverse the list forward and backward. Document the code and make sure to include an explanation of how the link list works. If the student adds additional features, he/she should document that as well. In testing the list, show what happens in the case of the NULL list. Show why this type list is easier to search than a single-linked list.

Answer 1

Note:

The code explained below deals with

1. Two types of insertions in a Double Linked List(In some places referred as D.L.L).

2. Forward and reverse traversal of a D.L.L

Solution:

In the images below a basic idea of a double linked list is provided, the code is provided at the end.

Code:

//The code is explained for a test case, you can perform any number of insertions.

#include <stdio.h>

#include <stdlib.h>

  

// A Typical Double Linked List Node

struct Node {

int data;

struct Node* next;

struct Node* prev;

};

  

/*New node at the beginning*/

void push(struct Node** head, int data)

{

/* 1. allocate a new node */

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

  

/* 2. put in the data */

temp->data = data;

  

/* 3. Make next of new node as head and previous as NULL */

temp->next = (*head);

temp->prev = NULL;

  

/* 4. change prev of head node to new node */

if ((*head) != NULL)

(*head)->prev = temp;

  

/* 5. move the head to point to the new node */

(*head) = temp;

}

  

  

/* New node at the end */

void append(struct Node** head, int data)

{

/* 1. allocate node */

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

  

struct Node* last = *head; /* used in step 5*/

  

/* 2. put in the data */

temp->data = data;

  

/* 3. This new node is going to be the last node, so

make next of it as NULL*/

temp->next = NULL;

  

/* 4. If the Linked List is empty, then make the new

node as head */

if (*head == NULL) {

temp->prev = NULL;

*head = temp;

return;

}

  

/* 5. Else traverse till the last node */

while (last->next != NULL)

last = last->next;

  

/* 6. Change the next of last node */

last->next = temp;

  

/* 7. Make last node as previous of new node */

temp->prev = last;

  

return;

}

// This function prints contents of linked list starting from the given node

void printList(struct Node* node)

{

struct Node* last;

printf("\nTraversal in forward direction \n");

while (node != NULL) {

printf(" %d ", node->data);

last = node;

node = node->next;

}

//Since the pointer is now at the end we can go back using 'last'

printf("\nTraversal in reverse direction \n");

while (last != NULL) {

printf(" %d ", last->data);

last = last->prev;

}

}

/* Main Function to test the functionality*/

int main()

{

/* Start with the empty list */

struct Node* head = NULL;

// Insert 6.

append(&head, 6);

// Insert 7 at the beginning.

push(&head, 7);

// Insert 1 at the beginning.

push(&head, 1);

// Insert 4 at the end.

append(&head, 4);

//The list now is 1->7->6->4->NULL

printf("Created DLL is: ");

printList(head);

return 0;

}

Advantages over Single Linked List:

1. We can traverse a DLL in both directions.

2. We can insert a new node before a specific node easily.

3. The DELETE operation can be performed more efficiently.