L
is empty
L
is non-empty
L
will remain
unchanged. Instead, you will have to traverse the list in
order to get to the last node, and then set the last
node's next
to point to a new node that you
create.
add2back
function that works in just this way.
#include <iostream> using namespace std; struct Node { string data; Node *next; }; void add2front(string d, Node *&L) { Node *T = new Node; T->data = d; T->next = L; L = T; } |
void add2back(string d, Node* &L) { Node* newlast = new Node; newlast->data = d; newlast->next = NULL; if (L == NULL) { // empty L case L = newlast; } else { // non-empty L case Node* last = L; while(last->next != NULL) last = last->next; last->next = newlast; } } |
int main() { Node *L = NULL; string s; while(cin >> s && s != ";") add2back(s,L); for(Node* p = L; p != NULL; p = p->next) cout << p->data << ' '; cout << endl; return 0; } |
If we want to take advantage of the add2front
function we already have, we can simplify this code a little
bit ... or at least we can make it shorter. I'll let you
decide for yourselves whether or not you think it is simpler.
void add2back(string d, Node* &L) { if (L == NULL) add2front(d,L); else { Node* last = L; while(last->next != NULL) last = last->next; add2front(d,last->next); } }
L
that is a pointer — a pointer to the first node in the
list. Now, if you look at the next
member of that
first node (i.e. look at L->next
), what is that?
It's a pointer — a pointer that represents the list of
everything after the first node.
So, for example, in the following linked list
The pointer L
is the list 5,9,2,8,4, and just as much
the pointer L->next
is the list 9,2,8,4.
This makes it natural for a recursive function called with
argument L
to make its recursive call with
argument L->next
.
We saw the example of such a recursive call with the recursive
version of length:
int length(Node* L) { if (L == NULL) return 0; return 1 + length(L->next); }Hopefully this makes sense now that we see that
L
is the list L->next
plus one extra node, the
node with data value 5.
Most other recursive functions with lists work the same way.
For example, suppose we want to calculate the sum of the
elements of list L. In the above example, it is
5 + the sum of 9,2,8,4. In other words,
L->data
plus the sum of the elements of
the list L->next
. So the recursive case is:
return L->data + sum(L->next);If you're printing out the list L from the example above recursively, you think of printing 5, then printing the list 9,2,8,4. So the recursive case for
print(L)
is
cout << L->data << ','; print(L->next);If you want to find the maximum element of L recursively, you think about comparing the data value of the first node with the maximum of the list of the remaining elements. Assuming you have a function
int max(int,int);
, you'd have
something like this:
return max(L->data,maxelt(L->next));Of course to make complete recursive functions, you need base cases as well.
int sum(Node* L) { if (L == NULL) return 0; else return L->data + sum(L->next); } |
void print(Node* L) // requires L non-empty { if (L->next == NULL) cout << L->data; else { cout << L->data << ','; print(L->next); } } |
int maxelt(Node* L) // requires L non-empty { if (L->next == NULL) return L->data; else return max(L->data,maxelt(L->next)); } |
L
is actually the same as adding to the back
of list L->next
Moreover, if L
is empty, adding to the back is the
same as adding to the front. Those two observations give us the
following recursive formulation which, I hope you'll admit, is
really beautiful!
void add2back(string d, Node* &L) { if (L == NULL) add2front(d,L); else add2back(d,L->next); }
next
to point to the old head node.
Adding a new node to the back of the list is more difficult,
because we must first create a temporary pointer and set it to
point to the last node in the list (tail), and this means
traversing our entire list from front to back. This is a lot of
work if you're going to be adding new nodes to the back
frequently, so it is sometimes nice to keep a second pointer that
points to the tail of the list, along with the pointer to the head
of the list that we always have. So, if we're talking about
linked lists of int
s, we might have something like
the following, which simply reads positive ints from the user and
prints them back out in the same order they were entered:
void add2front(int val, Node* &head, Node* &tail) { Node* p = new Node; p->data = val; p->next = head; if (head == NULL) head = tail = p; else head = p; } |
void add2back(int val, Node* &head, Node* &tail) { if (head == NULL) add2front(val,head,tail); else { tail->next = new Node; tail = tail->next; tail->next = NULL; tail->data = val; } } |
int main() { Node* head, *tail; head = tail = NULL; cout << "Enter ints, end with 0: "; int temp; while(cin >> temp && temp > 0) add2back(temp,head,tail); cout << "you entered: " << endl; for(Node* p = head; p != 0; p = p->next) cout << p->data << endl; return 0; } |
Alternate implementation:
void add2back(int val, Node* &head, Node* &tail) { if (head == NULL) add2front(val,head,tail); else add2front(val,tail->next,tail); } |
Node*
. Instead, it consists of
two objects, local variables head
and
tail
. Whenever we see that a single entity in a program
consists of several local variables like this, we should begin to
think about wrapping them up in a struct
.
struct List { Node *head, *tail; };With this declaration, a list in our program is an object of this new type "
List
", and the above program changes to:
void add2front(int val, List &L) { Node* p = new Node; p->data = val; p->next = head; if (L.head == NULL) L.head = L.tail = p; else L.head = p; } |
void add2back(int val, List &L) { if (L.head == NULL) add2front(val,L); else { L.tail->next = new Node; L.tail = tail->next; L.tail->next = NULL; L.tail->data = val; } } |
int main() { List L; L.head = L.tail = NULL; cout << "Enter ints, end with 0: "; int temp; while(cin >> temp && temp > 0) add2back(temp,L); cout << "you entered: " << endl; for(Node* p = L.head; p != NULL; p = p->next) cout << p->data << endl; return 0; } |
struct Node { string data; Node *next, *prev; };Now we need to think about some of our basic list functions all over again. For the sake of practice, let's assume that we want to add to the back often, so we'll adopt the previous scheme of keeping pointers to both the front and the back of our list.
struct Node { string data; Node *next, *prev; }; struct List { Node *head, *tail; }; |
void add2front(int val, List &L) { Node* p = new Node; p->data = val; p->next = head; p->prev = 0; if (L.head == 0) L.head = L.tail = p; else { L.head->prev = p; L.head = p; } } |
int main() { List L; L.head = L.tail = 0; cout << "Enter ints, end with 0: "; int temp; while(cin >> temp && temp > 0) add2back(temp,L); cout << "In order, you entered: " << endl; for(Node* p = L.head; p != 0; p = p->next) cout << p->data << ' '; cout << endl; cout << "Reveresed, you entered: " << endl; for(Node* p = L.tail; p != 0; p = p->prev) cout << p->data << ' '; cout << endl; return 0; } |
void add2back(int val, List &L) { if (L.head == 0) add2front(val,L); else { Node *p = new Node; p->data = val; p->next = 0; p->prev = L.tail; L.tail->next = p; L.tail = p; } } |
Point
, write a program that reads a comma
separated list of data
points from the user (terminated by a semi-colon) and then
repeatedly asks the user for a reference point, and responds by
printing out average of the distances of the data points from
the reference point.
~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453
~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; List read was (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453
~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; Last element is (-0.8,-1.1) (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453
~/$ ./prog (0.5,-0.25), (1.3,2.8), (3.1,0.9), (-0.8,-1.1) ; Next to last element is (3.1,0.9) (2,3) average = 2.91075 (2,1.5) average = 2.21384 (2,0.5) average = 2.11915 (2,-0.5) average = 2.38453
insert_in_order
function for doubly linked lists.
deleteNode
function,
which takes a pointer to a node in a doubly linked list and
and removes that node from the list. Don't forget to delete
the node when you're done with it!