Basic Linked List Operations


Most linked list problems require a thorough understanding of basic operations on singly-linked lists. These operations include tracking the head element so the list doesn’t get lost, traversing the list, and inserting or deleting list elements. Again, these operations are trivial with a doubly-linked list, so the problems will almost always use singly-linked lists.

Tracking the Head Element

The head element of a singly-linked list must always be tracked; otherwise, the list will be lost in memory. This means that the pointer or reference to the head of the list must be updated when a new element is inserted ahead of the first element or when the existing first element is removed from the list. Tracking the head element becomes a problem when you alter the list inside a function or method, because the caller must be made aware of the new head element. For example, the following Java/C# code is incorrect because it fails to update the reference to the head of the list:

 public void insertInFront( ListElement list, Object data ){     ListElement l = new ListElement( data );     l.next = list; }

The correct solution is to return the new head element from the method:

 public ListElement insertInFront( ListElement list, Object data ){     ListElement l = new ListElement( data );     l.next = list;     return l; }

The caller simply updates its reference to the head element accordingly:

 Object data = ....; // data to insert ListElement head = ....; // reference to head head = insertInFront( head, data );

In C/C++ it’s easier to make mistakes with pointer misuse. Consider this C/C++ code for inserting an element at the front of a list:

 bool insertInFront( IntElement *head, int data ){     IntElement *newElem = new IntElement;     if( !newElem ) return false;     newElem->data = data;     head = newElem; // Incorrect!     return true; }

The preceding code is incorrect because it only updates the local copy of the head pointer. The correct version passes in a pointer to the head pointer:

 bool insertInFront( IntElement **head, int data ){     IntElement *newElem = new IntElement;     if( !newElem ) return false;     newElen->data = data;     *head = newElem; // Correctly updates head     return true; }

Tip 

In C++, the head pointer could also be passed in by reference.

Traversing

Often, you need to work with list elements other than the head element. Operations on any but the first element of a linked list require traversal of some elements of the list, and you must always check for the end of the list. The following traversal is wrong:

 public ListElement find( ListElement head, Object data ){     while( head.data != data ){         head = head.next;     }     return head; }

The preceding search method works fine as long as the object to find is actually in the list. If it isn’t, an error occurs when you travel past the last element. A simple change to the loop fixes the problem:

 public ListElement find( ListElement head, Object data ){     while( head != null && head.data != data ){         head = head.next;     }     return head; }

The onus is on the caller to check for a non-null return value. It may make more sense to throw an exception once the end of the list is reached.

Tip 

Always test for the end of a linked list as you traverse it.

Inserting and Deleting Elements

Because elements in a singly-linked list are maintained exclusively with links to the next element, any insertion or deletion of elements in the middle of a list requires modification of the previous element’s link. This may require a traversal of the list, because there’s no other way to find a preceding element. Special care must be taken when dealing with the head of the list. Here’s a C/C++ example showing how to delete an element:

 bool deleteElement( IntElement **head, IntElement *deleteMe ) {     IntElement *elem = *head;     if( deleteMe == *head ){ /* special case for head */         *head = elem->next;         delete deleteMe;         return true;     }     while( elem ){         if( elem->next == deleteMe ){             /* elem is element preceding deleteMe */             elem->next = deleteMe->next;             delete deleteMe;             return true;         }         elem = elem->next;     }     /* deleteMe not found */     return false; }

Tip 

Deletion and insertion require a pointer or reference to the element immediately preceding the deletion or insertion location.

Performing deletions raises another issue in C/C++. Suppose you want to remove all the elements from a linked list. The natural inclination is to use a single pointer to traverse the list, freeing elements as you go. A problem arises, however, when this is implemented. Do you advance the pointer or free the element first? If you advance the pointer first, then the freeing is impossible because you overwrote the pointer to the element to be freed. If you free the element first, advancing the pointer is impossible because it involves reading the next pointer in the element that was just freed. The solution is to use two pointers, as in the following example:

 void deleteList( IntElement **head ) {     IntElement *deleteMe = *head;     while( deleteMe ){         IntElement *next = deleteMe->next;         delete deleteMe;         deleteMe = next;     }     *head = NULL; }

Tip 

Deletion of an element always requires at least two pointer variables. In fact, insertion requires two pointer variables as well, but because one of them is used for an element in the list and the other for the pointer returned by the memory allocation call, there’s little danger of forgetting this in the insertion case.




Programming Interviews Exposed. Secrets to Landing Your Next Job
Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition (Programmer to Programmer)
ISBN: 047012167X
EAN: 2147483647
Year: 2007
Pages: 94

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net