Linked Lists: The Basics

Linked Lists -- Part 1
The Basics


Click here for important instructions on how to print this web page.


Terminology

 
linked list
a list consisting of items in which each item knows the location of the next item.
node
an item in a linked list. Each node contains a piece of list data and the location of the next node (item).
link
(of a node) the location of the next node.
head node
first node in a linked list
head pointer
points to the head node


Linked list algorithms

The pseudo code to describe the algorithms uses these terms


Problems:

  1. Create an empty list.

    head = null

     

  2. Determine if a list is empty

    if (head == null)
       // list is empty

     

  3. Find an item (x) in a list

    p = head
    while p is not null and p->info is not x
      access p->info
      p = p->link


  4. Add an item (x) to a list. Define p as a pointer to a new node with x as info.
    • x goes to the front

      p->info = x
      p->link = head
      head = p

    • x goes to the middle or end. (This pseudo code assumes the list is ordered.)
      Use two pointers: current and previous

      p->info = x
      current = head
      while current is not null and current->info < x
         previous = current
         current = current->link
      if current is head

          p->link = head
          head = p
      else

          previous->link = p
          p->link = current

       

  5. Remove an item from a list
    (Change the link of the previous node to point to the node after the current node, or null, if there is no node after the current node. Then, destroy the current node)

    current = head
    while current is not null and current->info is not x
        previous = current
        current = current->link

    if current is not null
        if current points to the first node

            head = current->link
        if current does not point to the first node

            previous->link = current->link
        destroy the current node

When writing linked list algorithms, always look at special cases:

  • Empty list
  • List with 1 element
  • Activity at the beginning of the list
  • Activity at the end of the list
  • Activity will not occur (ex: The item is not in the list)
.