CS 102 Lecture Notes

Week Seven, Tuesday: Linked Lists

Fundamentals of Linked Lists

Linked lists store data items in "nodes" that are "linked" to each other in a chain (sequence or list) by pointers. The node contains the data item (or object) and the pointer to the next node in the list. The text example uses a struct for the node, but using a class would be more in keeping with the OOP (object oriented paradigm). However, to avoid confusion, we will use the MS text example code.

The "head" is the first node in the list. The "tail" is the last. Some implementations connect the head to the tail to make a "ring." This way, any valid node will have a non-null pointer (for defensive programming error checking).

Linked lists are convenient for many types of problems, but have the drawback that one can access a particular node only from one adjacent to it.

A Linked List Toolkit

Ten fundamental linked list functions:
  1. Get the length of a linked list.
  2. Insert a new node at the head of the linked list.
  3. Insert a new node after a given node.
  4. Search for an item in the linked list.
  5. Return the pointer to a node at a specified position in the linked list.
  6. Copy a linked list.
  7. Copy a portion of a linked list.
  8. Remove the node at the head of a linked list.
  9. Remove a node at a specified position in the linked list.
  10. Clear the linked list.

This page established September 29, 1999; last updated September 29, 1999.