Editing Linked list (section)

====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>.