Tuesday, September 19, 2006 and Thursday, September 21, 2006

Linked Lists

Topics

What is a linked list data structure?
    - A collection of data objects in dynamic memory that are "chained" together
    - Each data object contains a pointer to the next data object in the chain
    - List contains a beginning and ending point
    - The only size limit for the list is the size of the heap.  It can keep growing as long as the heap has room.
     - A common example might include reading records from a file when you don't know beforehand how many records there are.
 

How do we implement a linked list?
    - Each data object contains the data it is designed to hold, and  a pointer to the next object in the chain.
    - This is sometimes hard for students to get used to.  It looks like there is an object inside itself.  But remember that the "next object" pointer is just a pointer, not the object itself.  A pointer is just an address of where the next object is in dynamic memory.  It is only 4 bytes long (all pointers are 4 bytes on current computers).
    - Linked lists also must have a pointer to the first object in the chain, often called "head" or "list".
    - Sometimes linked lists also keep a pointer to the last object in the chain, often called the "tail".  
 

Example  .h file
class ListNode
{
public:
    ListNode(int);

    void setData(int);
    int getData();
    void setNext(ListNode*);
    ListNode* getNext();     

private:
    int data;
    ListNode* next;
};
 

Example  .c file

ListNode::ListNode(int d)
{
    data = d;
    next = NULL;
}
 

void ListNode::setData(int d)
{
    data = d;
}
 

int ListNode::getData()
{
    return data;
}
 

void ListNode::setNext(ListNode* n)
{
    next = n;
}
 

ListNode* ListNode::getNext()
{
    return next;
}
 

int main()
{
    int i;
    ListNode *head = NULL;
    ListNode *tail = NULL;
    ListNode *newnode, *current;
     

    for (i = 0; i < 10; i++)
    {
        newnode = new ListNode(i);
        if (head == NULL)
        {
            head = newnode;
            tail = head;     
        }
        else
        {
            tail->setNext(newnode);
            tail = newnode;
        }
    }

    current = head;
    while(current != NULL)
    {
        cout << current->getData();
        cout << "  ";
       
        current = current->getNext(); 
    }
    cout << endl;

    return 0;
}

Output
0 1 2 3 4 5 6 7 8 9  
 

How do we use a linked list?
    - Maintaining a beginning and ending point for the list
    - Adding to the list
    - Looping through the list to perform some common operation on each object
    - Removing objects from the list? (left as exercise)
    - Inserting objects from the list? (left as exercise)
 

Use of  friend  to access private data in list nodes   
    - Often the  friend   statement is used inside a list node class to give another class or function the ability to access private instance variables directly.
    - The  friend   statement violates good Object Oriented Design.  This technique should be used very carefully and not abused.

Example  .h file
class ListNode
{
    friend int main();
public:
    ListNode(int);

private:
    int data;
    ListNode* next;
};
 

Example  .c file

int main()
{
    int i;
    ListNode *head = NULL;
    ListNode *tail = NULL;
    ListNode *newnode, *current;
     

    for (i = 0; i < 10; i++)
    {
        newnode = new ListNode(i);
        if (head == NULL)
        {
            head = newnode;
            tail = head;     
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
    }

    current = head;
    while(current != NULL)
    {
        cout << current->data;
        cout << "  ";
       
        current = current->next; 
    }
    cout << endl;

    return 0;
}

Output
0 1 2 3 4 5 6 7 8 9  
 

Insertion and deletion into a linked list

   
    - Insertion into a linked list is very easy, as long as you have a pointer to the node you want to insert after.  It is simply a matter of reassigning two pointers.
    - Assume  current   is a pointer to a node and newnode   is a pointer to the new node.
    - First, you must assign the newnode->next pointer to point at what current->next points at.  This puts the new node logically before the node that follows current.
  - Next, simply make current->next   point at newnode. This makes the new node logically follow current.    

    - Deletion requires that you have a pointer to the node immediately before the node you want to delete.  If you have that pointer, however, it only requires that reassign its next pointer to delete the following node.  You must also return the following node to dynamic memory using the C++ delete keyword.
    - Assume  previous is a pointer to the node node before you want to delete.
    - First, you must put the previous->next pointer into a  temp pointer so you can return it to dynamic memory in the third step.
    - Second you must skip the node that follows the previous pointer by the assignment: previous->next = previous->next->next;
   - Chaining pointers together, as in previous->next->next, is a common practice and works quite well in C. 
   -  Finally return the node to dynamic memory using delete temp;   Notice that you must use the temp and you cannot just delete previous->next because previous->next has changed.  If you tried to delete previous->next before it changed, you could not then properly use previous->next = previous->next->next.
 

Example  .h file
class ListNode
{
    friend int main();
public:
    ListNode(int);

private:
    int data;
    ListNode* next;
};
 

Example  .c file

int main()
{
    int i;
    ListNode *head = NULL;
    ListNode *tail = NULL;
    ListNode *newnode, *current, *previous;
   

    /* create a linked list with 10 nodes */

    for (i = 0; i < 10; i++)
    {
        newnode = new ListNode(i);
        if (head == NULL)
        {
            head = newnode;
            tail = head;     
        }
        else
        {
            tail->next = newnode;
            tail = newnode;
        }
    }

 

    /* print the linked list */

    current = head;
    while(current != NULL)
    {
        cout << current->data;
        cout << "  ";
       
        current = current->next; 
    }
    cout << endl;
 

    /* go to the fourth node */

    current = head;
    for (i = 0; i < 4; i++)
    {
        current = current->next; 
    }

    /* insert a new node with 29 in it */

    newnode = new ListNode(29);
    newnode->next = current->next;
    current->next = newnode;

    /* print the linked list */

    current = head;
    while(current != NULL)
    {
        cout << current->data;
        cout << "  ";
       
        current = current->next; 
    }
    cout << endl;


    /* go to the eighth node */

    previous = head;
    for(i = 0; i < 8; i++)
    {
        previous = previous->next; 
    }
   

    /* delete the node following previous */

    ListNode* temp;
    temp = previous->next;
    previous->next = previous->next->next;
    delete temp;
 

    /* print the linked list */

    current = head;
    while(current != NULL)
    {
        cout << current->data;
        cout << "  ";
       
        current = current->next; 
    }
    cout << endl;

    return 0;
}

Output

0 1 2 3 4 5 6 7 8 9
0 1 2 3 29 4 5 6 7 8 9
0 1 2 3 29 4 5 6 7 9 
 

    - If you are careful, the previous pointer is not necessary.  The following is code to insert into a linked list in proper numerical order.  It uses the same .h file and ListNode.cpp file as above.  

// needs ListNode header and cpp files to work

int main()
{
	ListNode* head = NULL, *current = NULL;
	ListNode* newnode = NULL;

	int userinput;

	cout << "Please enter a number, -1 to exit: ";
	cin >> userinput;
	fflush(stdin);

	while (userinput != -1)
	{

		newnode = new ListNode(userinput);

		// put at head if list is empty
		if (head == NULL)
			head = newnode;
		else // list is not empty
		{
			if (newnode->data <= head->data)
			{ // insert at head
				newnode->next = head;
				head = newnode;
			}
			else
			{ // insert in middle
				current = head;
				while (current->next != NULL && 
					 current->next->data <= newnode->data)
					current = current->next;
				newnode->next = current->next;
				current->next = newnode;
			}
		}

		// print the list code
		if (head == NULL)
			cout << "Empty List" << endl;
		else
		{
			current = head;
			while ( current != NULL)
			{
				cout << current->data << "  ";
				current = current->next;
			}
			cout << endl;
		}

		cout << "Please enter a number, -1 to exit: ";
		cin >> userinput;
		fflush(stdin);
	}

	return 0;
}

Readings

Deitel and Deitel Fifth Edition, 21.1 to 21.4.  Pay close attention to the conceptual parts, and especially the diagrams. Unfortunately this chapter is after the chapter on templates, which we have not covered yet.  Try to ignore the template code, but you may not find the example code in these readings helpful.

Deitel and Deitel Fourth Edition, 17.1 to 17.4.  Same caveats.