Editing Linked list (section)

==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 merely to 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. Although with internal storage the same data can be placed in multiple lists by including multiple ''next'' references in the node data structure, it would then be necessary to create separate routines to add or delete cells based on each field. It is possible to create additional linked lists of elements that use internal storage by using external storage, and having the cells of the additional linked lists store references to the nodes of the linked list containing the data.

In general, if a set of data structures needs to be included in linked lists, external storage is the best approach. If a set of data structures need to be included in only one linked list, then internal storage is slightly better, unless a generic linked list package using external storage is available. Likewise, if different sets of data that can be stored in the same data structure are to be included in a single linked list, then internal storage would be fine.

Another approach that can be used with some languages involves having different data structures, but all have the initial fields, including the ''next'' (and ''prev'' if double linked list) references in the same location. After defining separate structures for each type of data, a generic structure can be defined that contains the minimum amount of data shared by all the other structures and contained at the top (beginning) of the structures. Then generic routines can be created that use the minimal structure to perform linked list type operations, but separate routines can then handle the specific data. This approach is often used in message parsing routines, where several types of messages are received, but all start with the same set of fields, usually including a field for message type. The generic routines are used to add new messages to a queue when they are received, and remove them from the queue in order to process the message. The message type field is then used to call the correct routine to process the specific type of message.

===Example of internal and external storage===

To create a linked list of families and their members, using internal storage, the structure might look like the following:

 '''record''' ''member'' { ''// member of a family''
     ''member'' next;
     ''string'' firstName;
     ''integer'' age;
 }
 '''record''' ''family'' { ''// the family itself''
     ''family'' next;
     ''string'' lastName;
     ''string'' address;
     ''member'' members ''// head of list of members of this family''
 }

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

 aFamily := Families ''// start at head of families list''
 '''while''' aFamily ≠ '''null''' ''// loop through list of families''
     print information about family
     aMember := aFamily.members ''// get head of list of this family's members''
     '''while''' aMember ≠ '''null''' ''// loop through list of members''
         print information about member
         aMember := aMember.next
     aFamily := aFamily.next

Using external storage, the following structures can be created:

 '''record''' ''node'' { ''// generic link structure''
     ''node'' next;
     ''pointer'' data ''// generic pointer for data at node''
 }
 '''record''' ''member'' { ''// structure for family member''
     ''string'' firstName;
     ''integer'' age
 }
 '''record''' ''family'' { ''// structure for family''
     ''string'' lastName;
     ''string'' address;
     ''node'' members ''// head of list of members of this family''
 }

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

 famNode := Families ''// start at head of families 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
     famNode := famNode.next

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. This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure (''node''), and this language does not have parametric types.

As long as the number of families that a member can belong to is known at compile time, internal storage works fine. If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary.

===Speeding up search===
Finding a specific element in a linked list, even if it is sorted, normally requires O(''n'') time ([[linear search]]). This is one of the primary disadvantages of linked lists over other data structures. In addition to the variants discussed above, below are two simple ways to improve search time.

In an unordered list, one simple heuristic for decreasing average search time is the ''move-to-front heuristic'', which simply moves an element to the beginning of the list once it is found. This scheme, handy for creating simple caches, ensures that the most recently used items are also the quickest to find again.

Another common approach is to "[[index (database)|index]]" a linked list using a more efficient external data structure. For example, one can build a [[red–black tree]] or [[hash table]] whose elements are references to the linked list nodes. Multiple such indexes can be built on a single list. The disadvantage is that these indexes may need to be updated each time a node is added or removed (or at least, before that index is used again).

===Random-access lists===
A [[random access list|random-access list]] is a list with support for fast random access to read or modify any element in the list.<ref name="okasaki">{{cite book |last=Okasaki |first=Chris |date=1995 |title=Purely Functional Random-Access Lists |work=In Functional Programming Languages and Computer Architecture |publisher=ACM Press |pages=86–95 |url=http://cs.oberlin.edu/~jwalker/refs/fpca95.ps |format=PS |access-date=May 7, 2015}}</ref> One possible implementation is a [[skew binary random access list|skew binary random-access list]] using the [[skew binary number system]], which involves a list of trees with special properties; this allows worst-case constant time head/cons operations, and worst-case logarithmic time random access to an element by index.<ref name="okasaki"/> Random-access lists can be implemented as [[persistent data structure]]s.<ref name="okasaki"/>

Random-access lists can be viewed as immutable linked lists in that they likewise support the same O(1) head and tail operations.<ref name="okasaki"/>

A simple extension to random-access lists is the [[min-list]], which provides an additional operation that yields the minimum element in the entire list in constant time (without{{clarify|r=should be "disregarding"?|date=October 2011}} mutation complexities).<ref name="okasaki"/>