# FAQ > Linked List Issues

 Match All Any word(s). If you have any questions or comments,please visit us on the Forums. FAQ > Prelude's Corner > Linked List Issues This item was added on: 2004/09/26IntroductionWhat is a linked list?List processingList reversalList splicingList sortingList indexingSome useful techniquesIntroductionLinked lists are very useful data structures. They are used a great deal strictly as themselves, but they serve as a foundation for more complicated linked data structures. It can safely be said that if you don't understand linked lists intimately, you'll be lost with simple binary trees, and have no hope concerning the more complex structures such as sparse matrices.That said, this tutorial will talk about common (and uncommon) usage of linked lists as well as a little bit of theory. Not much though, I was always a practical person who preferred pseudocode to flowcharts. First and foremost, a refresher course (ignoring the fact that just above this tutorial are probably two more).What is a linked list?A linked list is basically a collection of items where each item points to the next one:``` |1| -> |2| -> |3| -> |4| -> |5| -> ~ ```This sequence usually ends with a special item value called a sentinel, most often it will be a simple null pointer. Each item is a structure with a pointer to a structure of the same type as the "next" pointer, the pointer that tells you where to find the next item in the collection:``` struct item { T data; struct item *next; }; ```This is simple and sufficient for lists that are only traveled unidirectionally (eg. from the first to the last), but if you want to go back to an item you came from, another pointer is required, called the "prev" pointer:``` struct item { T data; struct item *prev; struct item *next; }; ```By using the above structure, you can create lists of items that can be traveled both forward and backward. In other words, you can get to every item in the collection no matter where you are. It would look something like this:``` |1| |2| |3| |4| |5| ~ <- | | <- | | <- | | <- | | -> | | | | -> | | -> | | -> | | -> | | -> ~ ```Provided you can read my awful art, you'll notice that the prev pointers act the same way as the next pointers, for example there is a sentinel before the first item in the list to mark the end of the prev pointers. To access any item in the list you can use dereferencing:Go to the next item``` item = item->next; ```Go to the previous item``` item = item->prev; ```Go to the second item``` item = item->next->next; ```Go to yourself``` item = item->next->prev; ```Go to the end of a five item list and then back two items, then forward one``` item = item->next->next->next->next->prev->prev->next ```Now, while this link chaining can be fun (I even got a little carried away ), it's usually easier to use loops. Here is one common idiom for walking a list:``` for ( item = list; item != NULL; item = item->next ) { visit ( item ); /* visit does something with a single item */ } ```Pretty simple, you may even have noticed the similarity with another common C/C++ idiom, one for walking an array:``` for ( i = 0; i < size; i++ ) { visit ( array[i] ); } ```A little more should be said about the sentinel before we continue. There are three types of sentinel: a null pointer, a dummy node (an item with a special invalid value that can be used as a sentinel), and a circular link. The null pointer is simple enough, as is the dummy node, but what's a circular link? A circular link turns the list into a ring type structure where, when you get to the end and go to the next item, you're back at the front:``` ^----->--------->------->------>- | | | |1| |2| |3| |4| |5| -< | | <- | | <- | | <- | | -> | | | | -> | | -> | | -> | | -> | | >- ^ | | | -<---------<--------------<------ ```If you can follow that diagram, you're either as crazy as me, or you've got the concepts of a circular linked list down. A few basic conventions for each type of list are as follows (we'll use a single linked list (just next pointers) to keep it simple:Head pointer, null tail:``` Initialize: list = NULL; Insert n after item: if ( item == NULL ) { list = n; list->next = NULL; } else { n->next = item->next; item->next = n; } Delete after item: save = item->next; item->next = item->next->next; Traverse: for ( item = list; item != NULL; item = item->next ) ```Dummy head, null tail:``` Initialize: struct item list; list->next = NULL; Insert n after item: n->next = item->next; item->next = n; Delete after item: save = item->next; item->next = item->next->next; Traverse: for ( item = list->next; item != NULL; item = item->next ) ```Dummy head, dummy tail:``` Initialize: struct item list; struct item sentinel; list->next = sentinel; sentinel->next = sentinel; Insert n after item: n->next = item->next; item->next = n; Delete after item: save = item->next; item->next = item->next->next; Traverse: for ( item = list->next; item != sentinel; item = item->next ) ```Circular list:``` Initialize: list->next = list; Insert n after item: n->next = item->next; item->next = n; Delete after item: save = item->next; item->next = item->next->next; Traverse: item = list; do { /* Work with item */ item = item->next; } while ( item != head ); ```All linked lists will follow some combination of the above conventions, so if you can recognize them all, you'll be able to read elementary list processing code without fail and be able to follow the basic logic of more complex algorithms. A quick note about single linked lists and double linked lists before we continue. When inserting a single linked item into a list, you need to update two links, both next pointers:``` n->next = item->next; /* Set n's next pointer */ item->next = n; /* Set item's next pointer */ ```However, with a double linked list, the number of links you need to fix doubles. If it helps you to remember, a double linked list is twice the work. ``` n->prev = item; /* n's prev pointer */ n->next = item->next; /* n's next pointer */ n->next->prev = n; /* n's next->prev pointer */ n->prev->next = n; /* n's prev->next pointer */ ```Only after those four links have been fixed will the item be correctly inserted. However, if one of those links is a sentinel, you have a problem. So the correct code to insert a node anywhere into a double linked list is:``` n->prev = item; n->next = item->next; if ( n->prev != NULL ) n->prev->next = n; if ( n->next != NULL ) n->next->prev = n; ```List processingAll linked lists should be able to insert and delete an item. In fact, the minimal list library that I wrote for this tutorial has only four functions: insert, delete, find the first item and find the last item. Here is the header: ``` #ifndef PRELIST_H #define PRELIST_H typedef enum { BEFORE, AFTER } Direction; typedef struct element *Element; typedef struct element *List; struct element { Element prev; Element next; int data; }; Element first(Element iter); Element last (Element iter); List add (List list, Element iter, Element item, Direction dir); List rem (List list, Element iter); #endif ```Simple, isn't it? For code that maintains both a head and tail pointer, the first and last functions will never even be used! The only reason I put them there is because I'm usually too lazy to maintain head and tail pointers. But just so that you know the issues, regular use of first and last can be a big performance hit for large lists. However, since the lists will be small in this tutorial, the performance problems are acceptable. On to the code!List reversalOften, being able to reverse a list in place is a useful operation. For example, when I'm truly lazy I'll sort and then reverse the list to find the largest item. Reversing a single linked list is very simple, just walk the list and build a new one by removing an item from the front of the old list and inserting it into the front of the new list. The result is an algorithm that does this:``` 0: Old: 1->2->3->4->~ New: ~ 1: Old: 2->3->4->~ New: 1->~ 2: Old: 3->4->~ New: 2->1->~ 3: Old: 4->~ New: 3->2->1->~ 4: Old: ~ New: 4->3->2->1->~ ```Pseudocode for this algorithm is as easy to write as it is to visualize:``` sub reverse ( list ) hold done todo done = null todo = list while todo != null hold = todo->next todo->next = done done = todo todo = hold loop return done end sub ```For double linked lists, you also have to take the prev pointer into account, but with careful thinking, this only adds one line to the algorithm. Here is the C/C++ source for reversing a double linked list:``` List reverse ( List list ) { Element hold; Element done; Element todo; done = NULL; todo = list; while ( todo != NULL ) { hold = todo->next; todo->next = done; done = todo; todo = hold; done->prev = todo; /* Fix the prev link */ } return done; } ```List splicingWhen I was first learning linked lists, the idea of splicing a part of one list into another was difficult. I thought that it must have been a long and convoluted algorithm that was far beyond me. Of course, when I realized that splicing is almost exactly the same as inserting a single item, I was slightly embarrassed. Splicing in a single linked list is awkward, so it really should be avoided. Double linked list splicing is ridiculously easy for most applications. Here is my minimal list splice function:``` List splice ( List list, Element pos, Element first, Element last, Direction dir ) { assert ( list != NULL ); assert ( pos != NULL ); assert ( first != NULL ); assert ( last != NULL ); if ( dir == BEFORE ) { first->prev = pos->prev; last->next = pos; } else { first->prev = pos; last->next = pos->next; } if ( first->prev != NULL ) first->prev->next = first; if ( last->next != NULL ) last->next->prev = last; return list; } ```The conditional statements are there to determine whether to add before or after the item in the list to add to, and to cover for possible null pointers. For example, if you splice to the front of a list, first->prev will be NULL, so setting first->prev->next will probably cause a segmentation violation because you're dereferencing a null pointer. Without the checks, and assuming that we will be inserting before the item, we have this:``` List splice ( List list, Element pos, Element first, Element last ) { first->prev = pos->prev; last->next = pos; first->prev->next = first; last->next->prev = last; return list; } ```See why I was embarrassed? List sortingSorting a linked list is a fun exercise, so I'll leave the elementary sorting implementations up to the reader. I'm not going to give a detailed description of sorting because this tutorial is about linked lists, so here is the implementation of mergesort on my minimal list library:``` List sort ( List self, int (*compare) ( const Element a, const Element b ) ) { Element p, q; Element e, tail; int insize = 1; int nmerges; int psize, qsize; int i; if ( self == NULL ) return self; for (;; ) { p = self; self = NULL; tail = NULL; nmerges = 0; while ( p ) { nmerges++; q = p; for ( psize = 0, i = 0; i < insize && q != NULL; psize++, i++ ) q = q->next; qsize = insize; while ( psize > 0 || ( qsize > 0 && q != NULL ) ) { if ( psize == 0 ) { e = q; q = q->next; qsize--; } else if ( qsize == 0 || q == NULL ) { e = p; p = p->next; psize--; } else if ( compare ( p, q ) <= 0 ) { e = p; p = p->next; psize--; } else { e = q; q = q->next; qsize--; } if ( tail != NULL ) tail->next = e; else self = e; e->prev = tail; tail = e; } p = q; } tail->next = NULL; if ( nmerges <= 1 ) return self; insize *= 2; } } ```The mergesort algorithm is unchanged for linked lists, so you can open any book on algorithms and find out exactly how this code works. Mergesort is a good general sorting algorithm as it is guaranteed to run in NlogN time and has the advantage of stability. Competitors such as quicksort and heapsort are not stable, which is the deciding factor much of the time. Another alternative way of sorting a linked list is not obvious at first, but uses the fact that a binary tree is always sorted. Simply walk the list, removing the first item and inserting it into a binary tree. Then do an inorder traversal of the tree, inserting at the end of a new list. Often it makes sense to switch between data structures, despite what people may tell you. Which leads us to the next topic.List indexingIndexing a list is gives you the best of linked lists and arrays. You can insert and delete from a list easily and index an array easily. Of course, it takes some tweaking to get code that uses a list index to run efficiently and without a lot of awkward code, but it can be very useful. To make a list index, you need to know how many items are in the list. Then allocate a dynamic array of pointers to items and traverse the list, adding each item to the new array. Here is some simple code that does this:``` Element *make_index ( List list, int *n ) { Element item; Element *index; int count; count = 0; for ( item = list; item != NULL; item = item->next ) count++; *n = count; index = malloc ( count * sizeof *index ); count = 0; for ( item = list; item != NULL; item = item->next ) index[count++] = item; return index; } ```Note that indexing can be expensive if the list changes constantly. Updating the index requires two traversals of the list and a call to malloc. Also, if you err on the side of efficiency and don't update the index of a constantly changing list, you will eventually have problems with indexing an old list but expecting a current one. Use this trick with care.Some useful techniquesHere are a few interesting and sometimes useful techniques with linked lists:Count the number of items matching a search:``` int count ( List list, int find ) { int count = 0; while ( list != NULL ) { if ( list->data == find ) count++; } return count; } ```Get the Nth item in a list:``` Element getnth ( List list, int index ) { int i; for ( i = 0; i < index; i++ ) { list = list->next; if ( list == NULL ) return NULL; } return list; } ```Destroy an entire list:This is a tricky situation because you can't free an item and then move to the next item. Many people incorrectly believe that this will work just fine:``` void destroy ( List list ) { while ( list != NULL ) { free ( list ); list = list->next; } } ```The correct way is to use a save pointer so that you never access memory that has been released:``` void destroy ( List list ) { Element save; while ( list != NULL ) { save = list->next; free ( list ); list = save; } } ```Remove duplicates:``` void unique ( List list ) { Element curr = list; Element save; /* Empty list */ if ( curr == NULL ) return; while ( curr->next != NULL ) { if ( curr->data == curr->next->data ) { save = curr->next->next; free ( curr->next ); curr->next = save; } else curr = curr->next; } } ```Well, after all of that you're probably wanting to see my minimal list library implementation, so to cap off the tutorial, here is the source code for List.c:``` #include #include #include "List.h" static void insBefore ( Element iter, Element item ) { assert ( iter != NULL ); assert ( item != NULL ); item->prev = iter->prev; item->next = iter; if ( iter->prev != NULL ) iter->prev->next = item; iter->prev = item; } static void insAfter ( Element iter, Element item ) { assert ( iter != NULL ); assert ( item != NULL ); item->prev = iter; item->next = iter->next; if ( iter->next != NULL ) iter->next->prev = item; iter->next = item; } Element first(Element iter) { while ( iter != NULL && iter->prev != NULL ) iter = iter->prev; return iter; } Element last ( Element iter ) { while ( iter != NULL && iter->next != NULL ) iter = iter->next; return iter; } List add ( List list, Element iter, Element item, Direction dir ) { assert( item != NULL ); if ( list == NULL ) /* Empty list */ list = item; else { if ( iter == list && dir == BEFORE ) { /* Before head */ insBefore ( list, item ); list = item; } else { if ( dir == BEFORE ) /* Before internal node */ insBefore ( iter, item ); else /* After internal node */ insAfter ( iter, item ); } } return list; } List rem ( List list, Element iter ) { assert ( list != NULL ); assert ( iter != NULL ); if ( iter->prev != NULL ) iter->prev->next = iter->next; if ( iter->next != NULL ) iter->next->prev = iter->prev; if ( iter == list ) list = iter->next; free ( iter ); return list; } ```Not much bigger than the header, is it? Linked lists can be as simple or complex as you want them to be, but down at the core, they're a piece of cake. Have fun!

Script provided by SmartCGIs

Popular pages