Singly Linked Lists (1-Way Lists)

One-Way Lists (Singly Linked Lists)

Linked lists are a convenient way to store data for sequential access. This paper describes several design alternatives associated with 1-way linked lists.

Let's assume we want to store a list of integers. The following code illustrates a typical node in the list, and sets up a head pointer with a null value:

struct Node { Node *next; int value;

}; Node *head = NULL;

To add and remove items from the front of the list we'll define functions push_front and pop_front:

void push_front(int value) { Node *p = new Node; p->value = value; p->next = head; head = p;

}

void pop_front() { Node *p = head; head = head->next; delete p;

}

The following code segment traverses the list from front to back:

for (Node *p = head; p; p = p->next) cout value;

To add and remove items from the back of the list we need to know the address of the last node on the list so we can update its next pointer. The following version of push_back chains through the list until it reaches the last node, then inserts a new node.

void push_back(int value) { Node *p = new Node; p->value = value; p->next = NULL;

// find last node Node *last; for (last = head; last && last->next; last = last->next);

// insert at tail of queue

if (last)

last->next = p;

else

head = p;

// list must be empty

}

Since we have to traverse the list to find the last node, this algorithm executes in O(n) time. For faster access let's maintain a tail pointer that points to the last node on the list. First let's fix push_front and pop_front, incorporating tail pointer logic.

void push_front(int value) { Node *p = new Node; p->value = value; p->next = head; head = p; if (!tail) tail = p;

}

void pop_front() { Node *p = head; head = head->next; if (!head) tail = NULL; delete p;

}

Now we can add our push_back function:

void push_back(int value) { // construct new node Node *p = new Node; p->value = value; p->next = NULL;

// insert node if (tail)

tail->next = p; else

head = p; // list must be empty tail = p; }

To code pop_back, we need a pointer to the next-to-last node so we can update its next pointer. Then, if we do another pop_back, we'll need a pointer to the node before that. This is a neverending problem, so for this purpose the tail pointer won't suffice. Let's look at a recursive solution:

void pop_back(Node *&p) { if (!p->next) {

// p->next is NULL, so p points to the last node delete p;

// also, p is the previous "next" pointer // that points to this node, so set it to NULL p = NULL; } else { pop_back(p->next); } }

pop_back(head);

This is a classic case of tail recursion, and can be rewritten in an iterative manner:

void pop_back(Node **p) { // p points to successive "next" pointers // in each node, and *p is the "next" pointer itself while ((*p)->next) p = &((*p)->next);

// *p is the "next" pointer that points to the last node delete *p; *p = NULL; }

pop_back(&head);

However, both solutions suffer from the fact that we must traverse the entire list to delete the last element. Let's investigate some other problems. Suppose you wanted to traverse a list from back to front? The following recursive solution will accomplish this task:

void listBack(Node *p) { if (!p) return; listBack(p->next); cout value;

} listBack(head);

What happens if you reverse the last two lines of listBack? How much stack space do we use for our recusive solution?

Finally, let's see how we can insert a value on an ordered linked list. The first algorithm will be done iteratively:

void insert(Node *&head, int value) { // setup new node Node *p = new Node; p->value = value;

// find insertion point Node *prev = NULL; Node *curr = head; while (curr && value > curr->value) {

prev = curr; curr = curr->next; }

// insert after prev, before curr

if (prev)

prev->next = p;

else

head = p;

// no prev, insert as first node

p->next = curr;

}

insert(head, 3);

While scanning for the insertion point we maintain two pointers. When the insertion point is found, we have a pointer to the previous node, and can update it's next pointer. We can also code a recursive solution:

void insert(Node *&p, int value) { if (!p || value < p->value) { Node *x = new Node; x->value = value; x->next = p; p = x; } else { insert(p->next, value); }

}

insert(head, 3);

This solution is considerably shorter, but we recurse for every node traversed in the list. Not the best solution for a linked list.

In summary, 1-way linked lists work well for adding and deleting elements at the front of the list. If you maintain a tail pointer, you can easily add new elements to the list. Well, easily if you get the tail pointer logic correct. And, removing elements from the end of a list is problematic. Tail pointers aren't much help in this case, and the only solution is to walk the entire list, iteratively or recursively.

Traversing a list in reverse order can be done recursively, at the expense of n recursive calls. An obvious solution to this problem is to incorporate backward links, in addition to forward links, in each node. And, as we'll soon see, other issues, such as removing elements from the end of the list, are easily accomplished. As a bonus, the logic for 2-way linked lists is actually simpler.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download