This page was last updated January 30, 2002

Lists

Everyone knows what a "list" is. You make lists of tasks to accomplish and items to pick up at the grocery store. Lists are a convenient way to store data in a computer.

This page discusses the List Abstract Data Type (ADT) and looks at the algorithms for some of the operations on a linked list.

List defined: A List is an ADT which implies a linear relationship between a number of items. Lists may be ordered (sorted based on some key) or unordered (unsorted).

Most of the time, when you implement a List ADT you will do it as a linked list, that is, each task in the list will be implemented in a data structure which contains a pointer to the next structure in the list. Occasionally you may choose to implement a list as an array of structures. The Code Vault contains examples of both.

This page presents the algorithms for the most common ordered linked list functions. At the end of this page are links to the simple linked list implementation (the ToDoList) shown in class. There is one implementation of the list as an array and another with the list implemented as a linked structure.

The algorithms discussed below are for an ordered linked list. In this discussion the key used is an integer. If a string key had been used then you would have to use strcmp() to determine which key was "smaller". For string keys "smaller" means one key comes before another alphabetically.

List Operations

  1. Create a list.
  2. Empty an existing list.
  3. Add an item to a list.
  4. Remove an item from a list.
  5. Find an item in the list.
  6. Determine if the list is full.
  7. Determine if the list is empty.

The Algorithms

Inserting a node into a List

Purpose: Insert a new node into an ordered linked list based on the value of the key.
Brief: Set a pointer to the head of the list and one to follow along behind. Compare the key in the new node to the key in the node in the list. If the key in the new node is greater than the key in the node in the list then advance the pointers to the next node in the list. Continue until the insertion point is found. Set all pointers to insert the new node into the list. Reset the head of the list if the new item was inserted before the existing head.
Cases:
 (1) Inserting first node into an empty list.
(2) Inserting node at the head of the list.
(3) Inserting node at the tail of the list.
(4) Inserting node somewhere in the middle of the list.
Function Prototype:
void Insert(Nodetype *newNode);
Algorithm: 
If head of the list == NULL 		// head is a member variable
	set newNode as head of new list (head = newNode) (Case 1)
Else 
	set a temporary pointer to the head of the list
	set a back pointer to NULL
	Find position to insert new node
	Loop till location is found or temp pointer falls off the end of the list
		If newNode->key < temp->key location has been found
		else advance back to temp and temp to temp->next
	end loop
Insert the newNode
	If back == NULL insert newNode as new head of list (Case 2)
		newNode->next = head
		set newNode as head of new list (head = newNode)
	Else insert into middle of list or at end (Cases 3 and 4)
		newNode->next = temp
		back->next = newNode


Diagram of insert for Case 3.



Deleting a node from a List

Purpose: Delete a node from an ordered linked list.
Brief: Set a pointer to the head of the list and one to follow along behind. Compare the search key to the key in the node in the list. If the keys do not match then advance the pointers to the next node. If the keys do match then Set all pointers to remove the node from the list. Free the removed node. Reset the head of the list if the first node was the one deleted.
Cases:
 (1) Deleting node at the head of the list.
(2) Deleting node somewhere in the middle of the list.
(3) Deleting node at the end of the list.
(4) Node to delete was not found.
Function Prototype:
void Delete(KeyType key);
Algorithm: 
Set a temporary pointer to the head of the list and a back pointer to NULL
// Note: head is a member variable
Find position of node to delete
	Loop till location is found or temp pointer falls off the end of the list
		If newNode->key == temp->key location has been found
		else advance back to temp and temp to temp->next
	end loop
if temp == NULL node to delete was not found (Case 4)
	return with list unchanged
Delete the Node
	If back == NULL delete node at head of list (Case 1)
		head = head->next
		free node pointed to by temp
		reset new head of list
	Else delete from middle of list or at end (Cases 2 and 3)
		back->next = temp->next
		free node pointed to by temp


Diagram of delete for Case 2.



Searching a List

Purpose: Locate a node containing a specified key in a linked list.
Brief: Set a pointer to the head of the list and move the pointer, in turn, to each node in the list comparing the key in the node to the search key. Continue until the search key is found or the search fails.
Cases:
 (1) List is empty, nothing to search
(2) Search key is found
(3) Search key is not found
Function Prototype:
NodeType *Search(KeyType key);
Algorithm: 
If head == NULL 	// head is a member variable
    return NULL (Case 1)
Else
    set temp = head	
    Loop while temp NOT NULL
        If search key matches key in current node
            return pointer to current node (Case 2)
        else
            advance temp to temp->next
    End loop;
return NULL (Case 3)


There are a number of examples of code implementing lists in the Code Vault, or you can directly access the
ToDoList demo as an array
or the
ToDoList demo as a linked structure.