Linear Data Structures: Doubly Linked Nodes

Question 1

What are the components of a doubly linked node chain?

Answer 1

• A data item
• A reference to the next node
• A reference to the previous node

The first node has its ‘previous’ node reference set to null

The last node’s ‘next’ reference is set to null.

Question 2

How is the structure of a doubly linked list different from a single-linked node chain?

Answer 2

A doubly linked list node has a reference to both its previous node and next node. A single-linked node chain only has a reference to the next node.

The overall structure includes a list object that manages the nodes.

Question 3

Updates to do doubly-linked node insertion at the beginning

Answer 3

• The new node’s “next” reference is set to the current head node
• The head reference is updated to point to the new node
• The previous “head” node’s “previous” reference is updated to point to the new node

The new node’s ‘next’ reference is set to the current head node.

Question 4

Updates to do doubly-linked node insertion at the end

Answer 4

• The current last node’s “next” reference is set to the new node
• The new node’s “previous” reference is set to the current tail node
• The tail reference in the list object is updated to point to the new node

The new node’s ‘previous’ reference is set to the current tail node.

Question 5

Updates to do doubly-linked node insertion at the middle

Answer 5

• Update the ‘next’ reference of node before insertion point (P)
• Update the ‘previous’ reference of node after insertion point (Q)
• Set new node’s ‘next’ reference to Q
• Set new node’s ‘previous’ reference to P

Question 6

What is one disadvantage of doubly linked lists?

Answer 6

They use more space than singly linked lists, because of the additional node reference

Each node stores an additional reference.

Question 7

What are two advantages of doubly linked lists?

Answer 7

• Constant time insertion and deletion at both ends
• Support for cursors and iterators that can move both forwards and backwards

Question 8

How can a doubly-linked list improve the time complexity for insertion into the middle list?

Answer 8

It can reduce from O(n) to O(1) due to the ability to find the previous node in constant time

Question 9

What does extending the LinkedIterator class for doubly linked lists enable?

Answer 9

It enables both forward and backward movement

Methods must be added to support backward movement.