Linked List

Template:Rewrite

What a Linked List is and its advantages[]

A linked list is a data structure where every element contains both a 'value' and a link/reference/pointer to a 'next' element (and sometimes also one to a 'previous' element). The whole list is represented by a pointer/reference/link to the first element of the list (or a structure encapsulating this).

This has somewhat more bookkeeping than just storing things in an array, but it has the advantage that the indicies of values is not fixed. If you want to add an element at the start of the container, you'll have to move all other elements forward if you use an array, while in a list you can just create a new element pointing to the previous start of the list, and set the start of the list to point to this new element. Same goes for inserting or removing stuff in the middle of the list. You can also 'splice' a whole list into another list rather easily. In no case does the address of a node change, which is particularly useful if you need to keep pointers to elements through modificiations.

And now some disadvantages. It's all about performance of memory access and pointers. List items may be placed sparsely in memory causing too many CPU data cache misses.

For single linked list of up to N items with fixed order you can create continuous array of N items and gain speed. For list terminator there is just one counter of items in the list to compare with. Faster version of single linked list of up to N items with variable order is to create array of size 2*N where odds are values and evens are next item's position. It may be handy to leave zero position as list terminator because of condition check is short to type and still readable. Also the end of list logic needs just one memory access. Also preset the array's unused cells to reference self positions to aid in debugging. And also forward-backward linked list of up to N items is faster when created using array of size 3*N. Where +1 element is previous item index and +2 element is next item index. Of course, all of these methods can leave you with holes in the array, if you delete elements from the middle of the list.

Another method of speeding it up is by keeping a pool of nodes, presumably all allocated in the same area of memory. Then instead of malloc'ing (or similar) the node on the heap, you simply request a node from the pool, and instead of free'ing you return it to the pool. The pool can easy be kept as a simple singly linked list of the nodes. This method is particularly handy with the C++ Standard Libraries's std::list, because it can be done in the allocator. The Boost Pool library provides a ready-made pool allocator.

A Small Linked List Tutorial[]

One thing about linked lists is that there are several types of lists that can be made. The three major types of linked lists is the default single linked list, then there is the doubly-linked list, and the final major type is the circular linked list.

Give me a few days and I'll have a few tutorials up for you (asm2750)

Single Linked List[]

The advantages of a single linked list is that it is simple to create, and add/remove 'nodes'. However, its main disadvantage is that it can take a while to add/remove nodes due to a pointer only able to go one way.

Every linked list needs to have one node that has no value, but just points to the start of the list we call this the 'Head Node'. The end of the list must always point to NULL this is good programming behavour and ensures that the program using the list in that method will be more stable. Files:Sllist.JPG

The basic C++ structure of a single linked list is as follows:

// Data members

DT dataItem; // List data item (DT can be any data type, if classes are used in C++ , the DT can be strings, chars, and so on). ListNode *next; // Pointer to the next list node

A visual example of adding a note to a list. One common mistake is to link the nodes in the wrong order. First you want node B to point to node C then you want to break the link between node A and C and have node A point to node B. center

A visual example of deleteing a node from a list. One common mistake is deleteing node B before relinking A to C this causes the list to fail outright. center

Doubly-Linked List[]

The doubly-linked list has one major advantage, it is possible to move a pointer that reads the list back and forth which saves on time a great deal. However, there is more pointer bookkeeping involved Instead of changing two pointers in a single linked list, you now have to change four. The speed in how data is found/added/removed however is still a large step.

A visual example of a doubly linked list. Notice there're two nulls, one head, and each node has two pointers. There's usualy a second head pointer called the rear (tail) pointer which keeps up the other end of the list. center

A visual example of adding a node to a doubly linked list. Notice how four pointers need to be changed. A common mistake in adding an element is changing the pointers in the wrong order, you want to have the pointers of the node you are adding pointing to its neighbors first, and then you want its neighbors to point to it.

center

A common mistake in removing a node, is that the node is deleted without having its neighbors to point at each other. The best method to delete a node is have a temporary node pointing at the address of the soon to be deleted node, then have its neighbors to point at each other which involves only changing two pointers, and then deleting the node.

Circular Linked List[]

There are two types of circular linked list, single and double. Like its name, the end of the list points at the beginning so there is no need for null. The advantage about this is that there is no real end of the list, and you don't have to reset pointers much. However, you have to keep track of the beginning and end of the list or problems are going to arise in the program. center

Skip Lists[]

Whenever a linked list is searched, normally each and every item much be inspected until the correct node is found. This can be very slow. Normally, hash tables or other data structures are used instead to speed up access. A skip list fixed this drawback and is a list that has binary search time. Basically, it means that every lookup will eleminate about half or more of all nodes as possible matches. The way this is done is by inserting extra forward links at each node, but not all nodes have the same amount of forward links.

First, a decision must be made on the total number of nodes believed to ever be included in the list. Next, a span length must be chosen. The span length is the average span a forward link has. For example, if a span of 10 nodes is chosen, this would mean that there would be on average 10 times more forward links at the next lower level. Basically, this forward link will skip over ten lower level nodes. The level above will skip over 100 nodes. The one above that, 1000 nodes, etc.

Every time a new element is inserted, the number of forward links to include in this node must be chosen. This is done via a random number generator. Lets assume a maximum of 10,000 elements and a span of 10, this means that every node has 100% chance of having at least 1 forward link, 10% (1/span) chance of having at least 2 forward links, 1% (1/span²) chance of having at least 3 forward links, and finally 0.1% (1/span³) chance of having 4 forward links. The reason we stop at 4 is because 10⁵=10,000. This would skip over the entire list which is pointless, so one less than 5 is used, hence the number 4. The random number generator must be set up with these percentages. Normally, we just say that number 0 (1 entry) means 4 links, 1 to 10 (10 entries) means 3 links, 11 to 111 (100 entries) means 2 links and 112 to 1112 (1000 entries) means 1 link. So you would have your number generator produce numbers from 0 to 1112 inclusive and apply the number of links according to the ranges above.

For all this to work means that the list must be sorted. When searching for a certain element in the list, the first level is used skips over 1000 nodes at a time on average until one is found to be higher than the node seeked. Using the previous node (since the current one is too large), the next level down is used which can skip over 100 nodes on average. Keep repeating this until the last level. A worst case of searching through 40 nodes (10 at each level) instead of 10,000 is a worst case 250 times speedup in performance than regular linked lists. Best case is 2500 times speedup. Average is 500 times speedup. The larger the list, the better the speedup.

For very little extra memory, the access, insertion and deletion time can greatly speed up the performance of your linked list, sometimes even surpassing that of hash tables. Speed is always critical in games. Although a random number generator is used, over the long run, averages will win out and thus search times will average logaritmic times (if spans are higher than 2) which is far superior to even binary search times. See here for a java applet demonstration of a skip list.

A C++ Example of a Single Linked List[]

I asm2750, here by release this c++ class of a single linked list to public domain for learning and research purposes.

Please only use it for learning and research, since C++'s standard library already includes a linked list class that's more generic, has more features, and has a better interface.

Linked List Header (This was an example given to me by a book, called "C++ data structures" it is pretty much just a basic Linked List header found in most programs.

ifndef LIST_LNK_H
define LIST_LNK_H

//--------------------------------------------------------------------
//
//  listlnk.h
//
//  Class declarations for the linked list implementation of the
//  List ADT
//
//--------------------------------------------------------------------
//***************************************************************************
// Programmer: asm2750
// Comments: Implmentation code written by me, header written by author from a book of examples.
//***************************************************************************

include <new>
include <stdexcept>

using namespace std;
template < class DT >         // Forward declaration of the List class
class List;
// This class creates the nodes for linked lists
template < class DT >
class ListNode                // Facilitator class for the List class
{

 private:

   // Constructor
   ListNode ( const DT &nodeData, ListNode *nextPtr );

   // Data members
   DT dataItem;      // List data item
   ListNode *next;   // Pointer to the next list node

friend class List

;
};

//--------------------------------------------------------------------

// this class creates the list and managages it
template < class DT >
class List
{
  public:

    // Constructor
    List ( int ignored = 0 );

    // Destructor
    ~List ();

    // List manipulation operations
    void insert ( const DT &newData )        // Insert after cursor
        throw ( bad_alloc );
    void remove ()                           // Remove data item
        throw ( logic_error );
    void replace ( const DT &newData )       // Replace data item
        throw ( logic_error );
    void clear ();                           // Clear list

    // List status operations
    bool isEmpty () const;                   // List is empty
    bool isFull () const;                    // List is full

    // List iteration operations
    void gotoBeginning ()                    // Go to beginning
        throw ( logic_error );
    void gotoEnd ()                          // Go to end
        throw ( logic_error );
    bool gotoNext ()                         // Go to next data item
        throw ( logic_error );
    bool gotoPrior ()                        // Go to prior item
        throw ( logic_error );
    DT getCursor () const                    // Return item
        throw ( logic_error );

    // Output the list structure -- used in testing/debugging
    void showStructure () const;

    // In-lab operations
    void moveToBeginning ()                    // Move to beginning
        throw ( logic_error );
    void insertBefore ( const DT &newElement ) // Insert before cursor
        throw ( bad_alloc );

  private:

    // Data members
    ListNode

 *head,     // Pointer to the beginning of the list
                 *cursor;   // Cursor pointer
				
};

endif

Linked List Implmentation


include "listlnk.h"

//***************************************************************************
//NODE Constructor
//***************************************************************************
template < class DT >
ListNode

::ListNode( const DT &nodeData, ListNode *nextPtr) {
	
	dataItem = nodeData;
	next = nextPtr;	
}


//***************************************************************************
//Default List Constructor
//***************************************************************************
template < class DT >
List

::List(int ignored) {
	
	head = NULL;
	cursor = NULL;


}

//***************************************************************************
//Destructor Memeber
//***************************************************************************
template < class DT >
List

::~List() { 	
	
	ListNode

* tmp;
	
	cursor = NULL;
	while (head != NULL){
		tmp = head;
		head = head->next;
		delete tmp;
	}
}


// Adding and Removeing Implmentations
//***************************************************************************
//Method insert
//Description: Adds new node after cursor
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::insert(const DT &newData) throw ( bad_alloc ) {
	
	if(isFull())
		throw bad_alloc ("List is Full");

	// make new node
	ListNode

* newNode = new ListNode

(newData,NULL);

	// if the list is empty then just add the node
	if(head == NULL)
	head = newNode;
	// if the cursor is at the end of the list then add it to end of list
	else if(cursor->next == NULL)
		cursor->next = newNode;
	else // if the cursor is in the middle of the end then add the item, but change
	{	// pointers to include the new node
		ListNode

* tmp = cursor->next;
		newNode->next = tmp;
		cursor->next = newNode;
	}
	// move the cursor to the new node
	cursor = newNode;
}

//***************************************************************************
//Method remove
//Description: Removes node cursor is pointing to and fixes list accordingly
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::remove() throw  (logic_error) {

	if(isEmpty())
		throw logic_error ("List Empty");
	ListNode

* tmp = NULL; // make new temp pointer

	if(cursor == head){ // if cursor is at the start of the list
		tmp = head;		
		head = head->next;
		cursor = head;
	}
	else{ // if cursor is some where in the list
	tmp = cursor;
	cursor = head;
	// find previous node
	while(cursor->next != tmp)
		cursor = cursor->next;
	// fix the list to skip the node in question
	cursor->next = tmp->next;
	

	}

	// destroy the node
	delete tmp;
	// if the node deleted was at end of list, then move to front otherwise move to next node
	if(cursor == NULL)
	cursor = head;
	else
		cursor = cursor->next;
}

//***************************************************************************
//Method replace
//Description: Replaces value of node that cursor is pointing to
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::replace(const DT &newData) throw (logic_error) {
	
	if(isEmpty())
	throw logic_error ("List Empty");

	// just change nodes value
	cursor->dataItem = newData;
}

//***************************************************************************
//Method clear
//Description: Clears list
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::clear() throw (logic_error) {
	
	if(isEmpty())
		throw logic_error ("List Empty");

	// works just like destructor
ListNode

* tmp;
	cursor = NULL;	
	while (head != NULL){
		tmp = head;
		head = head->next;
		delete tmp;
	}
}

// Status Methods
//***************************************************************************
//Method isFull
//Description: Determines if the List is full or not
//
//Pre: List has been instantiated
//
//Post: Returns true if the List is full otherwise false
//***************************************************************************
template <class DT>
bool List

::isFull() const {
	

	// see if there is any memory left
	try {
	ListNode

* tmp = NULL;
		delete tmp;
		return false;
	}
	catch(std::bad_alloc){
		return true;
	}
}

//***************************************************************************
//Method isEmpty
//Description: Determines if the List is empty or not
//
//Pre: List has been instantiated
//
//Post: Returns true if the List is empty otherwise false
//***************************************************************************
template <class DT>
bool List

::isEmpty() const {
	return (head == NULL);
}


// Cursor Methods
//***************************************************************************
//Method gotoBeginning
//Description: Moves cursor to beginning of list
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::gotoBeginning() throw ( logic_error ) {

	if(isEmpty())
	throw logic_error ("List Empty");

	cursor = head;
}

//***************************************************************************
//Method gotoEnd
//Description: Moves cursor to end of list
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::gotoEnd() throw ( logic_error ) {

	if(isEmpty())
	throw logic_error ("List Empty");


	while(cursor->next !=NULL)
		cursor = cursor->next;
}
	
//***************************************************************************
//Method gotoNext
//Description: Moves cursor to next list item
//
//Pre: List has been instantiated
//
//Post: Returns true if it was able to move to next item
//***************************************************************************
template <class DT>
bool List

::gotoNext() throw ( logic_error) {
	if(isEmpty())
		throw logic_error ("List Empty");

	if(cursor->next == NULL)
		return false;
	
	cursor = cursor->next;
	return true;
}

//***************************************************************************
//Method gotoPrior
//Description: Moves cursor to previous list item
//
//Pre: List has been instantiated
//
//Post: Returns true if it was able to move to prior item
//***************************************************************************
template <class DT>
bool List

::gotoPrior() throw (logic_error) {

	if(isEmpty())
		throw logic_error ("List Empty");

	if(cursor == head)
		return false;

	ListNode

* tmp = cursor;

	cursor = head;
	while(cursor->next != tmp)
		cursor = cursor->next;
	
	return true;
}

//***************************************************************************
//Method getCursor
//Description: Returns the value of the cursor its pointing to
//
//Pre: List has been instantiated
//
//Post: Returns value of cursor's item
//***************************************************************************
template < class DT > 
DT List

::getCursor() const throw (logic_error) {

	if(isEmpty())
		throw logic_error ("List Empty");

	return cursor->dataItem;
}
	
template < class DT >
void List

:: showStructure () const

// Outputs the items in a list. If the list is empty, outputs
// "Empty list". This operation is intended for testing and
// debugging purposes only.

{
    ListNode

 *p;   // Iterates through the list

    if ( head == 0 )
       cout << "Empty list" << endl;
    else
    {
       for ( p = head ; p != NULL ; p = p->next )
		   if ( p == cursor )
              cout << "[" << p->dataItem << "] ";
           else
              cout << p->dataItem << " ";
       cout << endl;
    }
}


//***************************************************************************
//Method moveToBeginning
//Description: Moves cursors node to the start of the list, and fixes list accordingly
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::moveToBeginning() throw ( logic_error ) {

	if(isEmpty())
		throw logic_error ("List Empty");

	ListNode

* tmp = head;
	// find previous node
	while(tmp->next != cursor)
		tmp = tmp->next;
	// change previous nodes ptr to cursors next node
	tmp->next = cursor->next;
	// move the cursors node to the top of the list
	cursor->next = head;
	// move head to the top of the list
	head = cursor;
}

//***************************************************************************
//Method insertBefore
//Description: Adds an item before the cursors node
//
//Pre: List has been instantiated
//
//Post: None
//***************************************************************************
template <class DT>
void List

::insertBefore(const DT & newElement) throw ( bad_alloc ) {

	if(isFull())
		throw bad_alloc ("List is Full");

	// if this is the first item of the list, then just add it
	if(head == NULL){
		head = new ListNode

(newElement,NULL);
	cursor = head;}
	else {
		// make the new node after the cursors node
		ListNode

* tmp = new ListNode

(cursor->dataItem, cursor->next);
		cursor->next = tmp; // make cursors node point to new node
		cursor->dataItem = newElement;	// assign currsors node the new element
		
	}

	
}