Editing Linked list (section)

==Linked list operations==

When manipulating linked lists in-place, care must be taken to not use values that have been 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, ''null'' is used to refer to an end-of-list marker or [[sentinel value|sentinel]], which may be implemented in a number of ways.

===Linearly linked lists===

====Singly linked lists====

The node data structure will have two fields. There is also a variable, ''firstNode'' which always points to the first node in the list, or is ''null'' for an empty list.

 '''record''' ''Node''
 {
     data; ''// The data being stored in the node''
     ''Node'' next ''// A [[reference (computer science)|reference]]''<ref name=":0" /> to the next node, null for last node
 }

 '''record''' ''List''
 {
     ''Node'' firstNode ''// points to first node of list; null for empty list''
 }

Traversal of a singly linked list is simple, beginning at the first node and following each ''next'' link until reaching the end:

 node := list.firstNode
 '''while''' node not null
     ''(do something with node.data)''
     node := node.next

The following code inserts a node after an existing node in a singly linked list. The diagram shows how it works. Inserting a node before an existing one cannot be done directly; instead, one must keep track of the previous node and insert a node after it.

  [[File:CPT-LinkedLists-addingnode.svg|frame|center|Diagram of inserting a node into a singly linked list]]

 '''function''' insertAfter(''Node'' node, ''Node'' newNode) ''// insert newNode after node''
     newNode.next := node.next
     node.next    := newNode

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

 '''function''' insertBeginning(''List'' list, ''Node'' newNode) ''// insert node before current first node''
     newNode.next   := list.firstNode
     list.firstNode := newNode

Similarly, there are functions for removing the node ''after'' a given node, and for removing a node from the beginning of the list. The diagram demonstrates the former. To find and remove a particular node, one must again keep track of the previous element.

[[File:CPT-LinkedLists-deletingnode.svg|frame|center|Diagram of deleting a node from a singly linked list]]

 '''function''' removeAfter(''Node'' node) ''// remove node past this one''
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode

 '''function''' removeBeginning(''List'' list) ''// remove first node''
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next ''// point past deleted node''
     destroy obsoleteNode

Notice that <code>removeBeginning()</code> sets <code>list.firstNode</code> to <code>null</code> when removing the last node in the list.

Since it is not possible to iterate backwards, efficient <code>insertBefore</code> or <code>removeBefore</code> operations are not possible. Inserting to a list before a specific node requires traversing the list, which would have a worst case running time of O(n).

Appending one linked list to another can be inefficient unless a reference to the tail is kept as part of the List structure, because it is needed to traverse the entire first list in order to find the tail, and then append the second list to this. Thus, if two linearly linked lists are each of length <math>n</math>, list appending has [[asymptotic time complexity]] of <math>O(n)</math>. In the Lisp family of languages, list appending is provided by the <code>[[append]]</code> procedure.

Many of the special cases of linked list operations can be eliminated by including a dummy element at the front of the list. This ensures that there are no special cases for the beginning of the list and renders both <code>insertBeginning()</code> and <code>removeBeginning()</code> unnecessary, i.e., every element or node is next to another node (even the first node is next to the dummy node). In this case, the first useful data in the list will be found at <code>list.'''firstNode'''.next</code>.

===Circularly linked list===

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.

Circularly linked lists can be either singly or doubly linked.

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 ''firstNode'' and ''lastNode'', although if the list may be empty, there needs to be a special representation for the empty list, such as a ''lastNode'' variable which points to some node in the list or is ''null'' if it is empty; it uses such a ''lastNode'' here. This representation significantly simplifies adding and removing nodes with a non-empty list, but empty lists are then a special case.

====Algorithms====
Assuming that ''someNode'' is some node in a non-empty circular singly linked list, this code iterates through that list starting with ''someNode'':

 '''function''' iterate(someNode)
     '''if''' someNode ≠ '''null'''
         node := someNode
     '''do'''
         do something with node.value
         node := node.next
     '''while''' node ≠ someNode

Notice that the test "'''while''' node ≠ someNode" must be at the end of the loop. If the test was moved to the beginning of the loop, the procedure would fail whenever the list had only one node.

This function inserts a node "newNode" into a circular linked list after a given node "node". If "node" is null, it assumes that the list is empty.

 '''function''' insertAfter(''Node'' node, ''Node'' newNode)
     '''if''' node = '''null'''    // assume list is empty
         newNode.next := newNode
     '''else'''
         newNode.next := node.next
         node.next := newNode
     update ''lastNode'' variable if necessary

Suppose that "L" is a variable pointing to the last node of a circular linked list (or null if the list is empty). To append "newNode" to the ''end'' of the list, one may do

 insertAfter(L, newNode)
 L := newNode

To insert "newNode" at the ''beginning'' of the list, one may do

 insertAfter(L, newNode)
 '''if''' L = '''null'''
     L := newNode
This function inserts a value "newVal" before a given node "node" in O(1) time. A new node has been created between "node" and the next node, then puts the value of "node" into that new node, and puts "newVal" in "node". Thus, a singly linked circularly linked list with only a ''firstNode'' variable can both insert to the front and back in O(1) time.
 '''function''' insertBefore(''Node'' node, newVal)
     '''if''' node = '''null'''    // assume list is empty
         newNode := '''new''' Node(data:=newVal, next:=newNode)
     '''else'''
         newNode := '''new''' Node(data:=node.data, next:=node.next)
         node.data := newVal
         node.next := newNode
     update ''firstNode'' variable if necessary
This function removes a non-null node from a list of size greater than 1 in O(1) time. It copies data from the next node into the node, and then sets the node's ''next'' pointer to skip over the next node.
 '''function''' remove(''Node'' node)
     '''if''' node ≠ '''null''' and size of list > 1
         removedData := node.data
         node.data := node.next.data
         node.next = node.next.next
         '''return''' removedData
<!--PLEASE FIX THIS
As in doubly linked lists, "removeAfter" and "removeBefore" can be implemented with "remove(list, node.prev)" and "remove(list, node.next)".

example:
node 'tom' next pointing to node 'jerry'...till the last point at node 'fix'..
data in node 'fix' previous to node 'tom'...looping instruction..
-->

=== Linked lists using arrays of nodes ===
Languages that do not support any type of [[reference (computer science)|reference]] can still create links by replacing pointers with array indices. The approach is to keep an [[array data type|array]] of [[record (computer science)|record]]s, 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 records are also not supported, [[parallel array]]s can often be used instead.

As an example, consider the following linked list record that uses arrays instead of pointers:

 '''record''' ''Entry'' {
     ''integer'' next; ''// index of next entry in array''
     ''integer'' prev; ''// previous entry (if double-linked)''
     ''string'' name;
     ''real'' balance;
 }

A linked list can be built by creating an array of these structures, and an integer variable to store the index of the first element.

 ''integer'' listHead
 ''Entry'' Records[1000]

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:

{| class="wikitable"
|-
! Index
! Next
! Prev
! Name
! Balance
|-
| 0
| 1
| 4
| Jones, John
| 123.45
|-
| 1
| −1
| 0
| Smith, Joseph
| 234.56
|-
| 2 (listHead)
| 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, <code>ListHead</code> 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 <code>ListFree</code> 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 could be stored in the list.

The following code would traverse the list and display names and account balance:
 i := listHead
 '''while''' i ≥ 0 ''// loop through the list''
     print i, Records[i].name, Records[i].balance ''// print entry''
     i := Records[i].next

When faced with a choice, the 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 [[serialization|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.
* Naïve [[dynamic memory allocation|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.
* Seizing an entry from a pre-allocated array is faster than using dynamic memory allocation for each node, since dynamic memory allocation typically requires a search for a free memory block of the desired size.

This approach has one main disadvantage, however: it creates and manages a private memory space for its nodes. This leads to the following issues:
* It increases complexity of the implementation.
* Growing a large array when it is full may be difficult or impossible, whereas finding space for a new linked list node in a large, general memory pool may be easier.
* Adding elements to a dynamic array will occasionally (when it is full) unexpectedly take linear ([[Big-O notation|O]](n)) instead of constant time (although it is still an [[amortized analysis|amortized]] constant).
* Using a general memory pool leaves more memory for other data if the list is smaller than expected or if many nodes are freed.
For these reasons, this approach is mainly used for languages that do not support dynamic memory allocation. These disadvantages are also mitigated if the maximum size of the list is known at the time the array is created.