Editing Linked list (section)

==Basic concepts and nomenclature==
Each record of a linked list is often called an 'element' or '[[node (computer science)|node]]'.

The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'. The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields.

The 'head' of a list is its first node. The 'tail' of a list may refer either to the rest of the list after the head, or to the last node in the list. In [[Lisp (programming language)|Lisp]] and some derived languages, the next node may be called the '[[CAR and CDR|cdr]]' (pronounced {{IPA|/'kʊd.əɹ/}}) of the list, while the payload of the head node may be called the 'car'.

===Singly linked list===
Singly linked lists contain nodes which have a 'value' field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.

[[Image:Singly-linked-list.svg|frame|center|A singly linked list whose nodes contain two fields: an integer value (data) and a link to the next node]]

The following C language code demonstrates how to add a new node with the "value" to the end of a singly linked list:<syntaxhighlight lang="c" line>
// Each node in a linked list is a structure. The head node is the first node in the list.

Node *addNodeToTail(Node *head, int value) {
    // declare Node pointer and initialize to point to the new Node (i.e., it will have the new Node's memory address) being added to the end of the list.
    Node *temp  = malloc(sizeof *temp); /// 'malloc' in stdlib.
    temp->value = value; // Add data to the value field of the new Node.
    temp->next  = NULL; // initialize invalid links to nil.
    
    if (head == NULL) {
        head = temp;     // If the linked list is empty (i.e., the head node pointer is a null pointer), then have the head node pointer point to the new Node.
    }
    else {
        Node *p = head;   // Assign the head node pointer to the Node pointer 'p'.
        while (p->next != NULL) {
            p = p->next;    // Traverse the list until p is the last Node. The last Node always points to NULL.
        }
        p->next = temp; // Make the previously last Node point to the new Node.
    }
    
    return head;    // Return the head node pointer.
}
</syntaxhighlight>

===Doubly linked list===
{{Main|Doubly linked list}}
In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').

[[Image:Doubly-linked-list.svg|frame|center|A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node]]

A technique known as [[XOR linked list|XOR-linking]] allows a doubly linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages.

Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects.<ref name=":0">{{cite web|url=http://www.osronline.com/article.cfm?article%3D499 |title=The NT Insider:Kernel-Mode Basics: Windows Linked Lists |access-date=2015-07-31 |url-status=dead |archive-url=https://web.archive.org/web/20150923015150/http://www.osronline.com/article.cfm?article=499 |archive-date=2015-09-23 }}</ref> A common strategy for [[rootkits]] to evade detection is to unlink themselves from these lists.<ref>{{cite web |last=Butler |first=Jamie |last2=Hoglund |first2=Greg |title=VICE – Catch the hookers! (Plus new rootkit techniques) |url=https://www.cs.dartmouth.edu/~sergey/me/cs/cs108/rootkits/bh-us-04-butler.pdf |url-status=dead |archive-url=https://web.archive.org/web/20161001201702/https://www.cs.dartmouth.edu/~sergey/me/cs/cs108/rootkits/bh-us-04-butler.pdf |archive-date=2016-10-01 |access-date=2021-08-31}}</ref>

===Multiply linked list===
In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data arranged in a different order (e.g., by name, by department, by date of birth, etc.). While a doubly linked list can be seen as a special case of multiply linked list, the fact that the two and more orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.

===Circular linked list===
In the last node of a linked list, the link field often contains a [[Null pointer#Null pointer|null]] reference, a special value is used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case, the list is said to be 'circular' or 'circularly linked'; otherwise, it is said to be 'open' or 'linear'. It is a [[list]] where the last node pointer points to the first node (i.e., the "next link" pointer of the last node has the memory address of the first node).

[[Image:Circularly-linked-list.svg|frame|center|A circular linked list]]

In the case of a circular doubly linked list, the first node also points to the last node of the list.

===Sentinel nodes===
{{Main|Sentinel node}}
In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node.

===Empty lists===
An empty list is a list that contains no data records. This is usually the same as saying that it has zero nodes. If sentinel nodes are being used, the list is usually said to be empty when it has only sentinel nodes.

===Hash linking===
The link fields need not be physically part of the nodes. If the data records are stored in an array and referenced by their indices, the link field may be stored in a separate array with the same indices as the data records.

===List handles===
Since a reference to the first node gives access to the whole list, that reference is often called the 'address', 'pointer', or 'handle' of the list. Algorithms that manipulate linked lists usually get such handles to the input lists and return the handles to the resulting lists. In fact, in the context of such algorithms, the word "list" often means "list handle". In some situations, however, it may be convenient to refer to a list by a handle that consists of two links, pointing to its first and last nodes.

===Combining alternatives===
The alternatives listed above may be arbitrarily combined in almost every way, so one may have circular doubly linked lists without sentinels, circular singly linked lists with sentinels, etc.