Computer Algorithms I CS 305 Class Notes

Lecture Notes for Computer Algorithms I

28 October 2003 - Linked Lists

Linked lists
1. Linked lists provide a level of indirection between a sequence of values and the next-value relation.
  1. Manipulating the next-value relation is cheaper than manipulating the value sequence.
  2. Indirection adds cost to moving sequentially through the values.
Linked-list structure.
1. For each element in a linked list, we need to know
  1. The element's value.
  2. The element's next relationship; that is, the next element.
2. A linked-list element is represented by the linked-list node (or just node) data structure.
  1. A node contains fields for the value and next element.
    1. The next-element is a node pointer.
```
struct linked-list-node {
  std::string value;
  linked-list-node * next;
  }

linked-list-node * 
new-linked-list-node(std::string value, linked-list-node * next) {
  linked-list-node * np = new linked-list-node;
  np->value = value;
  np->next = next;
  return np;
  }
```
3. Assembling a linked list.
  1. At the least, a linked list consists of a pointer to the first element of the list.
    1. The first element of the linked list is also known as the head of the linked list.
    2. If the list is empty (contains no elements), the pointer is null.
  2. The last element of the linked list is also known as the tail of the linked list.
    1. The next field of the linked-list tail is the null pointer.
    2. The same element can be both the head and the tail.
  3. Other possible linked-list components.
    1. A pointer to the tail of the list.
      1. May be convenient to have; requires more work to maintain.
    2. A count of the number of elements in the list (size).
      1. Depending on other linked-list operations, size may be easy to maintain.
      2. Don't confuse size with empty; if empty's good enough, don't use size.
Linked-list operations.
1. Creating a new linked list.
  1. Set the head pointer to null
2. Testing for an empty linked list.
  1. Test the head pointer for null.
3. Searching for a value in a linked list.
  1. What should this return?
    1. A pointer to the element or a boolean?
```
linked_list_node *
find(Element value)
  for (linked_list_node * p = head; p; p = p->next)
    if (p->value == value)
      return p
  return 0
```
4. Inserting a new value in a linked list.
  1. The two questions are: Insert it where in the list? and Insert it how?
    1. Where in the list can be indicated by a pointer to an element or by an element value.
      1. You can use find() to turn an element value into an element pointer.
      2. An element pointer is unmabiguous.
        
        The first value? The last value? Some other value? What if there's no such value?
    2. Insert the new value before or after the indicated element?
      1. You want to be able to insert a value anywhere in the linked list.
        
        If you insert before the element, you can't insert at the end of the list.
        If you insert after the element, you can't insert at the beginning of the list.
      2. Allow the caller to choose before or after.
        
        Complicated to implement and to use.
      3. Pick before or after and special case (somehow) the problem insertion.
        
        Use the null pointer (for example) to indicate the problem.
        Special casing is bad, the notation is dangerous.
      4. Use a dummy node to ensure there's always an element to insert after (or before).
        
        To always insert after, use a dummy list head; to always insert before, use a dummy list tail.
        Dummy list heads require less machinery, and are preferred.
        
        Consequently, so is inserting after the element.
        A linked list is now a dummy list head pointing to the actual list head (if it exists).
        
        The value in the dummy list head doesn't matter.
  2. Assuming a pointer to the element to insert after, inserting is straightforward.
```
linked-list-node *
insert_after(linked-list-node * here, Element value)
  linked-list-node * np = new linked-list-node
  hp->value = value
  np->next = here->next
  here->next = np
  return np
```
5. Deleting a value from a linked list.
  1. Deleting is similar to inserting: delete an element with a value or delete a pointed-to node?
    1. It turns out it doesn't really matter.
  2. Deleting a node requires "splicing out" the node, which requires swimming up-stream.
    1. There is no pointer to the previous node.
  3. Traverse the list until you find the previous node; then splicing out is easy.
```
void
remove(linked-list-node * here) 
  for (prev = &head; prev->next != here; prev = prev->next) { }
  prev->next = here->next
  delete here;
```
    1. When deleting by value, you can look for the node and the previous node at the same time.
      1. But it's a bit more complicated.
  4. You can also delete after, which wouldn't require any traversal at all.
    1. But it's more complicated for the caller to use.
A linked-list ADT.
1. Implementing a linked list ADT is straightforward, except for the nodes.
  1. Each element type requries a new node structure.
  2. You'd like to hide nodes inside the ADT.
    1. But what about all those node pointers we've been passing around?
2. Define a typeless linked-list node; treat it as the linked list.
  1. Extend the typeless node with an element field when needed.
3. Or you can use templates, as Nyhoff demonstrates.
Further considerations.
1. Doubly-linked list.
2. Ganged node allocations.

This page last modified on 3 December 2003.