Exercises

* 8.7(a), 8.9(b), 8.11(a).

* Doing exercises is a good way to check if you really understand the stuff or not.

Reading Assignments

* Ch 12 - 12.5. (Wed)

* Ch 12.7 - end of Ch 12. (Fri)

Assignment #4

* a tough one.

* if stuck, get help!

* due Fri July 21.

class Node

class Node {

friend class List;

private:

Node(int x, Node* in_next);

...

private:

int data;

Node* next;

};

class List {

public:

void append(int x);

...

private:

Node* head;

};

Incorrect Code

void

List::append(int x)

{ if (head == NULL) {

head = new Node(x, NULL);

} else {

Node* p = head;

while (p) {

p = p->next;

}

p = new Node(x, NULL);

}

}

How does this work?

void

List::append(int x)

{ if (head == NULL) {

head = new Node(x, NULL);

} else {

Node* p = head;

while (p->next) {

p = p->next;

}

p->next = new Node(x, NULL);

}

}

Advantages

* save space (usually).

* certain operations (e.g. insert, delete) are simpler.

Variants of Dynamic Linked Lists

1. Head Nodes

2. Doubly Linked Lists

Head Nodes

* head pointer never needs to be changed.

* eliminates the special case for the first list node.

void

List::append(int x)

{

Node* p = head;

while (p->next) {

p = p->next;

}

p->next = new Node(x, NULL);

}

Head Nodes (cont'd...)

* traversal algorithms must skip the head node.

* the head node must not be deleted.

Implementation

* constructors construct the head node.

* head node is only destroyed when the destructor is implicitly called.

Advantages

* simpler algorithms.

Disadvantages

* extra node.

Doubly Linked Lists

* With singly linked lists, the predecessor of a node is not directly available.

* Doubly linked lists consists of nodes that have a previous pointer, in addition to the next pointer.

class Node {

friend class List;

Node(int in_data, Node* in_next, Node* in_prev);

int data;

Node* next;

Node* prev;

};

Node* head;

void

append(int x, Node* head)

{

if (!head) {

head = new Node(x, NULL, NULL);

} else {

Node* p = head;

while (p->next) {

p = p->next;

}

p->next = new Node(x, NULL, p);

}

}

Debugging Dynamic Linked Lists

* Common problems

1. Dangling pointers - may get run time error.

2. inaccessible objects - no run time error.

3. memory leaks - no run time error.

4. dereferencing null pointers - should get run time error.

* When a run time error is reported by the system, the real bug usually happens earlier.

* When a run time error is not reported, debugging becomes very difficult.

Suggestions

* draw diagrams of linked structures to analyze your algorithms.

* check assertions.

* avoid dangling pointers.

* don't increment pointers to dynamic node.

* We haven't talked about pointer arithmetic at all. So you probably won't do that anyway.

* set pointers to NULL when they are not pointing to anything.

* dump the lists (e.g. hw#4).

Disadvantages

* complex algorithm.

* waste space (in some cases).

* new and delete are expensive operations.

Dynamic Linked Lists