Linked Lists
A linked list is a collection of components, called nodes. Every node (except the last node)
contains the address of the next node. Thus, every node in a linked list has two components:
one to store the relevant information (that is, data) and one to store the address, called the
link, of the next node in the list. The address of the first node in the list is stored in a separate
location, called the head or first.
Linked list: A list of items, called nodes, in which the order of the nodes is determined
by the address, called the link, stored in each node.
struct nodeType
{
int info;
nodeType *link;
};
The variable declaration is as follows:
nodeType *head;
TRAVERSING A LINKED LIST
The basic operations of a linked list are as follows: Search the list to determine whether a
particular item is in the list, insert an item in the list, and delete an item from the list.
These operations require the list to be traversed. That is, given a pointer to the first node
of the list, we must step through the nodes of the list.
Suppose that the pointer head points to the first node in the list, and the link of the last
node is NULL. We cannot use the pointer head to traverse the list because if we use the
head to traverse the list, we would lose the nodes of the list. This problem occurs because
the links are in only one direction. The pointer head contains the address of the first
node, the first node contains the address of the second node, the second node contains the
address of the third node, and so on. If we move head to the second node, the first node
is lost (unless we save a pointer to this node). If we keep advancing head to the next
node, we will lose all the nodes of the list (unless we save a pointer to each node before
advancing head, which is impractical because it would require additional computer time
and memory space to maintain the list).
Therefore, we always want head to point to the first node. It now follows that we must
traverse the list using another pointer of the same type. Suppose that current is a pointer
of the same type as head.
The following code traverses the list:
current = head;
while (current != NULL)
{
//Process current
current = current->link;
}
For example, suppose that head points to a linked list of numbers. The following code
outputs the data stored in each node:
current = head;
while (current != NULL)
{
cout << current->info << ” “;
current = current->link;
}
BUILDING A LINKED LIST FORWARD
Suppose that the nodes are in the usual info-link form and info is of type int. Let us
assume that we process the following data:
2 15 8 24 34
We need three pointers to build the list: one to point to the first node in the list, which
cannot be moved, one to point to the last node in the list, and one to create the new
node. Consider the following variable declaration:
nodeType *first, *last, *newNode;
int num;
Suppose that first points to the first node in the list. Initially, the list is empty, so both
first and last are NULL. Thus, we must have the statements
first = NULL;
last = NULL;
to initialize first and last to NULL.
Next, consider the following statements:
1 cin >> num; //read and store a number in num
2 newNode = new nodeType; //allocate memory of type nodeType
//and store the address of the
//allocated memory in newNode
3 newNode->info = num; //copy the value of num into the
//info field of newNode
4 newNode->link = NULL; //initialize the link field of
//newNode to NULL
5 if (first == NULL) //if first is NULL, the list is empty;
//make first and last point to newNode
{
5a first = newNode;
5b last = newNode;
}
6 else //list is not empty
{
6a last->link = newNode; //insert newNode at the end of the list
6b last = newNode; //set last so that it points to the
//actual last node in the list
}
To maintain a linked list, we use two pointers—first and last. The pointer first points to the first node in the list, and last points to the last node in the list. We also keep a count of the number of nodes in the list. Therefore, the class linkedListType has three instance variables, as follows:
protected:
int count; //variable to store the number of elements in the list
nodeType *first; //pointer to the first node of the list
nodeType *last; //pointer to the last node of the list Linked List Iterators One of the basic operations performed on a list is to process each node of the list.
This requires the list to be traversed starting at the first node. Moreover, a specific application requires each node to be processed in a very specific way. A common technique to accomplish this is to provide an iterator. So what is an iterator? An iterator is an object that produces each element of a container, such as a linked list, one element at a time. The two most common operations on iterators are ++ (the increment operator) and * (the dereferencing operator). The increment operator advances the iterator to the next node in the list while the dereferencing operator returns the info of the current node. Note that an iterator is an object. So we need to define a class, which we will call linkedListIterator, to create iterators to objects of the class linkedListType. The iterator class would have one member variable pointing to (the current) node.
Linked List Iterators
One of the basic operations performed on a list is to process each node of the list. This
requires the list to be traversed starting at the first node. Moreover, a specific application
requires each node to be processed in a very specific way. A common technique to
accomplish this is to provide an iterator. So what is an iterator? An iterator is an object
that produces each element of a container, such as a linked list, one element at a time.
The two most common operations on iterators are ++ (the increment operator) and *
(the dereferencing operator). The increment operator advances the iterator to the next
node in the list while the dereferencing operator returns the info of the current node.
Note that an iterator is an object. So we need to define a class, which we will call
linkedListIterator, to create iterators to objects of the class linkedListType.
The iterator class would have one member variable pointing to (the current) node
template class linkedListIterator {
public: linkedListIterator();
//Default constructor
//Postcondition: current = NULL;
linkedListIterator(nodeType *ptr); //Constructor with a parameter. //Postcondition: current = ptr;
Type operator*(); //Function to overload the dereferencing operator *. //Postcondition: Returns the info contained in the node. linkedListIterator operator++(); //Overload the preincrement operator. //Postcondition: The iterator is advanced to the next node.
bool operator==(const linkedListIterator& right) const;
//Overload the equality operator. //Postcondition: Returns true if this iterator is equal to // the iterator specified by right, otherwise it returns //
false. bool operator!=(const linkedListIterator& right) const; //Overload the not equal to operator.
//Postcondition: Returns true if this iterator is not equal to
// the iterator specified by right, otherwise it returns // false.
private: nodeType *current; //pointer to point to the current //node in the linked list
};
Destroy List
The function destroyList deallocates the memory occupied by each node. We traverse the list starting from the first node and deallocate the memory by calling the operator delete. We need a temporary pointer to deallocate the memory. Once the entire list is destroyed, we must set the pointers first and last to NULL and count to 0.
template <class Type>
void linkedListType::destroyList() {
nodeType *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //while there are nodes in the list
{ temp = first;
//set temp to the current node
first = first->link;
//advance first to the next node delete temp;
//deallocate the memory occupied by temp }
last = NULL;
//initialize last to NULL; first has already //been set to NULL by the while loop count = 0; }
Initialize the List
The function initializeList initializes the list to an empty state. Note that the default constructor or the copy constructor has already initialized the list when the list object was declared. This operation, in fact, reinitializes the list to an empty state, and so it must delete the nodes (if any) from the list. This task can be accomplished by using the destroyList operation, which also resets the pointers first and last to NULL and sets count to 0.
template <class Type>
void linkedListType::initializeList() {
destroyList(); //if the list has any nodes, delete them
}
The function initializeList uses the function destroyList, which is of O(n). Therefore, the function initializeList is of O(n).
Print the List
The member function print prints the data contained in each node. To print the data contained in each node, we must traverse the list starting at the first node. Because the pointer first always points to the first node in the list, we need another pointer to traverse the list. (If we use first to traverse the list, the entire list will be lost.)
template <class Type>
void linkedListType::print() const { nodeType *current;
//pointer to traverse the list
current = first; //set current point to the first node while (current != NULL) //while more data to print { cout << current->info << ” “;
current = current->link; }
}//end print As in the case of the function destroyList, the function print is of O(n).
Length of a List
The length of a linked list (that is, how many nodes are in the list) is stored in the variable count. Therefore, this function returns the value of this variable.
template <class Type>
int linkedListType::length() const { return count; }
Retrieve the Data of the First Node
The function front returns the info contained in the first node, and its definition is straightforward.
template
Type linkedListType::front() const {
assert(first != NULL);
return first->info; //return the info of the first node
}//end front Notice that if the list is empty, the assert statement terminates the program. Therefore, before calling this function check, you have to check to see whether the list is nonempty.
Retrieve the Data of the Last Node
The function back returns the info contained in the last node. Its definition is as follows:
template<class Type>
Type linkedListType::back() const {
assert(last != NULL);
return last->info;
//return the info of the last node
}//end back Notice that if the list is empty, the assert statement terminates the program. Therefore, before calling this function, you have to check to see whether the list is nonempty. From the definitions of the functions length, front, and back, it follows easily that each of these functions are of O(1).
Copy The List:
The function copyList makes an identical copy of a linked list. Therefore, we traverse
the list to be copied starting at the first node. Corresponding to each node in the original
list, we do the following:
1. Create a node and call it newNode.
2. Copy the info of the node (in the original list) into newNode.
3. Insert newNode at the end of the list being created.
The definition of the function copyList is as follows:
template <class Type>
void linkedListType<Type>::copyList
(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType<Type>; //create the node
first->info = current->info; //copy the info
first->link = NULL; //set the link field of the node to NULL
last = first; //make last point to the first node
current = current->link; //make current point to the next
// node
//copy the remaining list
while (current != NULL)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of newNode to NULL
last->link = newNode; //attach newNode after last
last = newNode; //make last point to the actual last
//node
current = current->link; //make current point to the
//next node
}//end while
}//end else
}//end copyList
The function copyList contains a while loop. The number of times the while loop
executes depends on the number of items in the list. If the list contains n items, the while
loop executes n times. Therefore, the function copyList is of O(n).
Destructor:
The destructor deallocates the memory occupied by the nodes of a list when the class
object goes out of scope. Because memory is allocated dynamically, resetting the pointers
first and last does not deallocate the memory occupied by the nodes in the list. We
must traverse the list, starting at the first node, and delete each node in the list. The list
can be destroyed by calling the function destroyList. Therefore, the definition of the
destructor is as follows:
template <class Type>
linkedListType<Type>::~linkedListType() //destructor
{
destroyList();
}
Search the List
The member function search searches the list for a given item. If the item is found, it
returns true; otherwise, it returns false. Because a linked list is not a random access
data structure, we must sequentially search the list starting from the first node.
This function has the following steps:
1. Compare the search item with the current node in the list. If the info of
the current node is the same as the search item, stop the search; otherwise,
make the next node the current node.
2. Repeat Step 1 until either the item is found or no more data is left in the
list to compare with the search item.
template <class Type>
bool unorderedLinkedList<Type>::
search(const Type& searchItem) const
{
nodeType<Type> *current; //pointer to traverse the list
bool found = false;
current = first; //set current to point to the first
//node in the list
while (current != NULL && !found) //search the list
if (current->info == searchItem) //searchItem is found
found = true;
else
current = current->link; //make current point to
//the next node
return found;
}//end search
The number of times the while loop executes, in the function search, depends on where
in the list the search item is located. Suppose the list has n items. If the search item is not in
the list, the while loop executes n times. On the other hand, if the search item is the first
item, the while loop executes 1 time. Similarly, if the search item is the ith item in the list,
the while loop executes i times. From these observations, we can show that the function
search is of O(n).
Doubly Linked Lists:
A doubly linked list is a linked list in which every node has a next pointer and a back
pointer. In other words, every node contains the address of the next node (except the last
node), and every node contains the address of the previous node (except the first node).A doubly linked list can be traversed in either direction. That is, we can traverse the list
starting at the first node or, if a pointer to the last node is given, we can traverse the list
starting at the last node.
As before, the typical operations on a doubly linked list are as follows: Initialize the list,
destroy the list, determine whether the list is empty, search the list for a given item, insert
an item, delete an item, and so on.
Circular Linked Lists
A linked list in which the last node points to the first node is called a circular linked list.
In a circular linked list with more than one node, as in Figure 5-34(c), it is convenient to
make the pointer first point to the last node of the list. Then by using first you can
access both the first and the last node of the list.
For example, first points to the last node and first->link points to the first node.
As before, the usual operations on a circular list are as follows: Initialize the list (to an
empty state), determine if the list is empty, destroy the list, print the list, find the length of
the list, search the list for a given item, insert an item in the list, delete an item from the
list, and copy the list.
