* 8.1(a,b), 8.2(a,b), 8.3(a), 8.4(a,c), 8.6(a).

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

Reading Assignment

* Finish Ch 8.

* Have you really been reading the text?

Assignment #4

* a tough one.

* start early.

* due Fri July 21.

Lists

* In hw#3, you've coded an array implementation of a list sorted in the alphabetical order of the names of the items. You've observed:

1. Accessing elements using subscripts is quite convenient.

2. Inserting and removing elements require extensive data movement in the array.

* If we need to make inserting and removing elements more efficient, we may choose a linked-list implementation.

Linked Lists

* A linked list is a collection of "nodes", each containing at least one member that gives the location of the "next" node in the list.

* In the simplest case, each node has two members: the data value of the list item and a value locating the successor of this node.

* Example, a list of three integers:

Dynamic data implementations of linked lists

* The Node class

class Node {

...

int data;

Node* next; // Even though Node hasn't been

// fully declared yet, its pointer type can

// be used.

};

* The List class

class List {

...

Node* head;

};

Forward declaration (an example)

// .h file

class Node;

class List {

...

Node* head; // again, the Node pointer type can

//  be used.

};

// .cpp file

class Node {

...

};

Dynamic allocation of list nodes

head = new Node;

head->data = 100;

head->next = new Node;

head->next->data = 20;

head->next->next = NULL;

Exercises

* What is the type of each of the following?

1. head

2. *head

3. head->data

4. head->next

5. *head->next

6. head->next->data

7. head->next->next

8. *head->next->next

Length of a list (Note: non-member function)

(iterative version)

int

length(const Node* head)

{

Node* p = head;

int size = 0;

while (p != NULL) {

size++;

p = p->next;

} return size;

}

// assume you can access data members of Node

// i.e., assume this is a friend function

(recursive version)

int

length(const Node* head)

{ if (head == NULL) { // base case

return 0;

} else { // recursive case

return 1 + length(head->next);

} }

Membership (Note: non-member function)

(iterative version)

Boolean

is_member(int x, const Node* head)

{

Node* p = head;

while (p != NULL) { if (p->data == x) {

return TRUE;

} else {

p = p->next;

}

} return FALSE;

}

(recursive version)

Boolean

is_member(int x, const Node* head)

{ if (head == NULL) { // base case

return FALSE;

} elsif (head->data == x) { // base case

return TRUE;

} else { // recursive case

return is_member(x, head->next);

}

}