Linked Lists -- Part 1
Click here for important
instructions on how to print this web page.
- linked list
- a list consisting of items in which each item knows the location of the next
- an item in a linked list. Each node contains a piece of list data and the location
of the next node (item).
- (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
- head = pointer to the first list item (head node).
- info = node data
- link = node link
- null = pointer that is not an actual address
- p = pointer to a node
- Create an empty list.
head = null
- Determine if a list is empty
if (head == null)
// list is empty
- Find an item (x) in a list
p = head
while p is not null and p->info is not x
p = p->link
- Add an item (x) to a list. Define p as a pointer to a new node
with x as info.
- 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)