* 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