Doubly-Linked List and Project 1

Chapter 16

What if we want to traverse the list in reverse?

Three Options:

1. We can use recursion to iterate to the end and then perform the operation when we “unwind.”

2. We can use a helper data structure (a stack).

3. We can implement a doubly-linked list type, where every node has a next and previous pointer.

   

   Example of a doubly-linked list.

   

   Example of a doubly-linked list.

Prepending a Doubly-Linked List

Step 0:

Initial State before prepending to a doubly-linked list.

Initial State before prepending to a doubly-linked list.

Step 1:

Create the new node.

Create the new node.

Step 2:

Update pNewNode->pNext to mpHead.

Update pNewNode->pNext to mpHead.

Step 3:

Update mpHead->pPrev to pNewNode.

Update mpHead->pPrev to pNewNode.

Step 4:

Update mpHead to pNewNode.

Update mpHead to pNewNode.

Appending a Doubly-Linked List

Step 0:

Initial State before appending to a doubly-linked list.

Initial State before appending to a doubly-linked list.

Step 1:

Create the new node.

Create the new node.

Step 2:

Update pNewNode->pNext to mpTail.

Update pNewNode->pNext to mpTail.

Step 3:

Update mpTail->pNext to pNewNode.

Update mpTail->pNext to pNewNode.

Step 4:

Update mpTail to pNewNode.

Update mpTail to pNewNode.

Intro. to the Standard Template Library (SLT)

Go here for lecture notes on the STL.

Homework

• Lab 9: Doubly-Linked Lists

• Project 1: Large Map