3.1 Linked lists vs. arrays

Linked lists have several advantages over arrays. They allow a new element to be inserted or deleted at any position in a constant number of operations (changing some references), while arrays require a linear ( O(n)) number of operations. Elements can also be inserted into linked lists indefinitely, while an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller.

Further memory savings can be achieved, in certain cases, by sharing the same "tail" of elements among two or more lists — that is, the lists end in the same sequence of elements. In this way, one can add new elements to the front of the list while keeping a reference to both the new and the old versions — a simple example of a persistent data structureIn computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, bu.

On the other hand, arrays allow random access, while linked lists allow only sequential accessIn computer science sequential access means that a group of elements (e. data in a memory array or a disk file or on a tape) is accessed in a predetermined, ordered sequence. Sequential access is sometimes the only way of accessing the data, for example i to elements. Singly-linked lists, in fact, can only be traversed in one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsortHeapsort is one of the best general-purpose sort algorithms, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O n log n runtime and. Also, arrays benefit from ideal cache behavior when its elements are traversed in order; ordinary linked lists don't benefit from the cache at all.

Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as charactersFor alternate meanings, see character. In computer terminology, a character is a unit of information that roughly corresponds to a grapheme, or written symbol, of a natural language, such as a letter, numeral, or punctuation mark. The concept also include or boolean values. It can also be slow, and with a naive allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pool s.

A number of linked list variants exist that aim to ameliorate some of the above problems. Unrolled linked listAn unrolled linked list is a variation on the linked list which stores multiple elements in each node. It can drastically increase cache performance, while decreasing the memory overhead associated with storing list metadata such as references. It is relas store several elements in each list node, increasing cache performance while decreasing memory overhead for references. CDR coding does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record.

3.2 Double-linking vs. single-linking

Double-linked lists require more space per node (unless one uses xor-linking), and their elementary operations are more expensive; but they are often easier to manipulate because they allow sequential access to the list in both directions. In particular, one can insert or delete a node in a constant number of operations given only that node's address. Some algorithms, such as quicksort, require access in both directions. On the other hand, they do not allow tail-sharing, and cannot be used as persistent data structures.

3.3 Circular lists

Circular linked lists are most useful for describing naturally circular structures, and have the advantage of regular structure and being able to traverse the list starting at any point. They also allow quick access to the first and last records through a single pointer (the address of the last element). Their main disadvantage is the complexity of iteration, which has subtle special cases.

3.4 Sentinel nodes

Sentinel nodes may simplify certain list operations, by ensuring that the next and/or previous nodes exist for every element. However sentinel nodes use up extra space (especially in applications that use many short lists), and they may complicate other operations.

4 Linked list operations

When manipulating linked lists in-place, care must be taken to not use values that you have invalidated in previous assignments. This makes algorithms for inserting or deleting linked list nodes somewhat subtle. This section gives pseudocode for adding or removing nodes from singly, doubly, and circularly linked lists in-place. Throughout we will use null to refer to an end-of-list marker or sentinel, which may be implemented in a number of ways.

4.1 Singly-linked lists

Our node data structure will have two fields. We also keep a variable head which always points to the first node in the list, or is null for an empty list.

The following is wikicode , a proposed pseudocode for use in many articles:

record Node { data // The data being stored in the node; often a reference to the actual data next // A reference to the next node } Node head // points to front of list Node nodeBeingRemoved // used in later examples

Traversal of a singly-linked list is easy:

node := head // start at front of list while node not null { // loop through list (do something with node.data) node := node.next // go to next node in list }

The following code inserts a node after an existing node in a singly linked list. Inserting a node before an existing one cannot be done; instead, you have to locate it while keeping track of the previous node.

function insertAfter(Node node, Node newNode) { // insert newNode after node newNode.next := node.next // point new node to next node node.next := newNode // add new node to list }

Inserting at the beginning of the list requires a separate function. This requires updating head.

function insertBeginning(Node newNode) { // insert node before current head newNode.next := head // point to rest of list head := newNode // new front of list }

Similarly, we have functions for removing the node after a given node, and for removing a node from the beginning of the list. To find and remove a particular node, one must again keep track of the previous element.

function removeAfter(Node node) { // remove node past this one nodeBeingRemoved := node.next // this is the node to delete node.next := node.next.next // point past node (the above statement could be node.next = nodeBeingRemoved.next) destroy nodeBeingRemoved // free up deleted node } function removeBeginning(Node node) { // remove head node nodeBeingRemoved := head // this is the node to delete head := head.next // point past deleted node destroy nodeBeingRemoved // free up deleted node }

Notice that removeBeginning() sets head to null when removing the last node in the list.

4.2 Doubly-linked lists

With doubly-linked lists there are even more pointers to update, but also less information is needed, since we can use backwards pointers to observe preceding elements in the list. This enables new operations, and eliminates special-case functions. We will add a prev field to our nodes, pointing to the previous element, and a tail variable which always points to the last node in the list. Both head and tail are null for an empty list.

Iterating through a doubly linked list can be done in either direction. In fact, direction can change many times, if desired.

Forwards

node := head while node ≠ null node := node.next

Backwards

node := tail while node ≠ null node := node.prev

These symmetric functions add a node either after or before a given node:

function insertAfter(node, newNode) newNode.prev := node newNode.next := node.next if node.next = null tail := newNode else node.next.prev := newNode node.next := newNode function insertBefore(node, newNode) newNode.prev := node.prev newNode.next := node if node.prev is null head := newNode else node.prev.next := newNode node.prev := newNode

We also need a function to insert a node at the beginning of a possibly-empty list:

function insertBeginning(newNode) if head = null head := newNode tail := newNode newNode.prev := null newNode.next := null else insertBefore(head, newNode)

A symmetric function inserts at the end:

function insertEnd(newNode) if tail = null insertBeginning(newNode) else insertAfter(tail, newNode)

Removing a node is easier, only requiring care with head and tail:

function remove(node) if node.prev = null head = node.next else node.prev.next = node.next if node.next = null tail := node.prev else node.next.prev = node.prev destroy node

One subtle consequence of this procedure is that deleting the last element of a list sets both head and tail to null.

4.3 Circularly-linked lists

Circularly-linked lists can be either singly or doubly linked. In a circularly linked list, all nodes are linked in a continuous circle, without using null. For lists with a front and a back (such as a queue), one stores a reference to the last node in the list. The next node after the last node is the first node. Elements can be added to the back of the list and removed from the front in constant time.

Both types of circularly-linked lists benefit from the ability to traverse the full list beginning at any given node. This often allows us to avoid storing head and tail, although if the list may be empty we need a special representation for the empty list, such as a head variable which points to some node in the list or is null if it's empty; we use such a head here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.

Assuming that someNode is some node in a non-empty list, this code iterates through that list starting with someNode:

Forwards

node := someNode do do something with node.value node := node.next while node &neq; someNode

Backwards

node := someNode do do something with node.value node := node.prev while node &neq; someNode

Notice the postponing of the test to the end of the loop. This is important for the case where the list contains only the single node someNode.

This simple function inserts a node into a doubly-linked circularly linked list after a given element:

function insertAfter(node, newNode) newNode.next := node.next newNode.prev := node node.next.prev := newNode node.next := newNode

Inserting an element in a possibly empty list requires a special function:

function insertBeginning(node) if head = null node.prev := node node.next := node else insertAfter(head.prev, node) head := node

Finally, removing a node must deal with the case where the list empties:

function remove(node) if node.next = node head := null else node.next.prev := node.prev node.prev.next := node.next destroy node

5 Linked lists using arrays of nodes

Languages that don't support any type of reference can still create links by replacing pointers with array indices. The approach is to keep an array of records, where each record has integer fields indicating the index of the next and (possibly) previous node in the array. Not all nodes in the array need be used. If even records are not supported, parallel arrays can often be used instead.

As an example, consider the following type structure in Visual Basic:

TYPE foo Next as Integer Prev as Integer ' if a double linked list is desired Name as String Balance as Float END TYPE

By creating an array of these structures, and an integer variable to store the index of the head element, a linked list can be built:

Dim ListHead as Integer Dim FooBar(1000) as foo

Links between elements are formed by placing the array index of the next (or previous) cell into the Next or Prev field within a given element. For example:

Index	Next	Prev	Name	Balance
0	1	4	Jones, John	123.45
1	-1	0	Smith, Joseph	234.56
2	4	-1	Adams, Adam	0.00
3			Ignore, Ignatius	999.99
4	0	2	Another, Anita	876.54
5
6
7

In the above example, ListHead would be set to 2, the location of the first entry in the list. Notice that entry 3 and 5 through 7 are not part of the list. These cells are available for any additions to the list. By creating a ListFree integer variable, a free list could be created to keep track of what cells are available. If all entries are in use, the size of the array would have to be increased or some elements would have to be deleted before new entries can be stored in the list.

Advantages of this approach include:

• The linked list is relocatable, meaning it can be moved about in memory at will, and it can also be quickly and directly serialized for storage on disk or transfer over a network.
• Especially for a small list, array indexes can occupy significantly less space than a full pointer on many architectures.
• Locality of reference can be improved by keeping the nodes together in memory and by periodically rearranging them, although this can also be done in a general store.
• Naive dynamic memory allocators can produce an excessive amount of overhead storage for each node allocated; almost no allocation overhead is incurred per node in this approach.

This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. Not only does this increase complexity of the implementation, but growing it may be difficult or impossible, because it is large, whereas finding space for a new linked list node in a large, general memory pool is easier. This slow growth also affects algorithmic performance, as it causes a few insert operations to unexpectedly take linear ( O(n)) instead of constant time (although it's still amortized constant). Using a general memory pool also leaves more memory for other data if the list is smaller than expected or if many nodes are freed.

6 Language support

Many programming languages such as Lisp and Scheme have singly linked lists built in. In many functional languages, these lists are constructed from nodes, each called a cons or cons cell. The cons has two fields: the car, a reference to the data for that node, and the cdr, a reference to the next node. Although cons cells can be used to build other data structures, this is their primary purpose.

In other languages, linked list are typically built using references together with records. Here is a complete example in C:

#include /* for printf */ #include /* for malloc */ typedef struct ns { int data; struct ns *next; } node; node *list_add(node ** p, int i) { node *n = malloc(sizeof(*n)); n->next = *p; *p = n; n->data = i; return n; } void list_remove(node ** p) { if (p) { node *n = *p; *p = (*p)->next; free(n); } } node **list_search(node ** n, int i) { if (!n) return NULL; while (*n) { if ((*n)->data == i) { return n; } n = &(*n)->next; } return NULL; } void list_print(node * n) { if (!n) printf("list is empty\n"); while (n) { printf("print %p %p %i \n", n, n->next, n->data); n = n->next; } } int main(void) { node *n = NULL; list_add(&n, 0); list_add(&n, 1); list_add(&n, 2); list_add(&n, 3); list_add(&n, 4); list_print(n); list_remove(&n); /* remove head */ list_remove(&n->next); /* remove second */ list_remove(list_search(&n, 1)); list_remove(&n->next); /* remove tail */ list_remove(&n); /* remove last */ list_print(n); return 0; }

7 Internal and external storage

When constructing a linked list, one is faced with the choice of whether to store the data of the list directly in the linked list nodes, called internal storage, or to merely store a reference to the data, called external storage. Internal storage has the advantage of making access to the data more efficient, requiring less storage overall, having better locality of reference, and simplifying memory management for the list (its data is allocated and deallocated at the same time as the list nodes).

External storage, on the other hand, has the advantage of being more generic, in that the same data structure and machine code can be used for a linked list no matter what the size of the data is. It also makes it easy to place the same data in multiple linked lists. Note, however, that even with internal storage the same data can be placed in multiple lists, either by including multiple next references in the node data structure, or by having other linked lists store references to the nodes of the linked list containing the data.

A common misconception is that every list using internal storage requires a new set of functions to operate on the linked list, consuming more effort and code space than an approach using external storage. This is true with a naive approach, but as long as the next pointers are located in the same place in each record, it is possible to create a generic implementation of linked lists with internal storage that only needs to be supplied for each type of list a way of creating and destroying nodes.

7.1 Example

Suppose you wanted to create a linked list of families and their members. Using internal storage, the structure might look like the following:

record member { // structure for a member of a family member next // pointer to other members of family string fname // first name integer age // age of member } record family { // structure for the family itself family next // pointer to other families string lname // last name of family string address // address of family string phone // phone number of family member members // pointer to list of members of family }

To print a complete list of families and their members using internal storage, we could write:

aFamily := Families // start at head of list while aFamily ≠ null { // loop through list of families print information about family aMember := aFamily.members // get list of family members while aMember ≠ null { // loop through list of members print information about member aMember := aMember.next // to to next member } aFamily := aFamily.next // go to next family }

Using external storage, we would create the following structures:

record node { // generic link structure node next // pointer to next node pointer data // generic pointer for data at node } record member { // structure for family member string fname // first name integer age // age of member } record family { // structure for family string lname // last name of family string address // address of family string phone // phone number of family node members // pointer to list of members of family }

To print a complete list of families and their members using external storage, we could write:

famNode := Families // start at head of list while famNode ≠ null { // loop through list of families aFamily = (family)famNode.data // extract family from node print information about family memNode := aFamily.members // get list of family members while memNode ≠ null { // loop through list of members aMember := (member)memNode.data // extract member from node print information about member memNode := memNode.next // get next family member } famNode := famNode.next // get next family in list }

Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type.

8 Related data structures

The skip list is a linked list augmented with layers of pointers for quickly jumping over large numbers of elements, and then descending to the next layer. This process continues down to the bottom layer, which is the actual list.

A binary tree can be seen as a type of linked list where the elements are themselves linked lists of the same nature. The result is that each node may include a reference to the head node of one or two other linked lists, which, together with their contents, form the subtrees below that node.

An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance, since more list elements are contiguous in memory, and reduced memory overhead, because less metadata needs to be stored for each element of the list.

9 External links

• Description from the Dictionary of Algorithms and Data Structures
• Some linked list materials are available from the Stanford Computer Science department :
  • Introduction to Linked Lists
  • Linked List Problems
• Citations from CiteSeer

data structures

<Hide>