A linked data structure is a collection of data arranged in a list-like format. Each piece of datum in the list is referred to as a node. Each node is connected to the next one on the list by a reference to the memory address of that subsequent node. Linked data structures are used in place of an array when the number of nodes on a list is unknown or might grow or shrink over the course of the execution of the program. The most common type of linked data structure is called a linked list.
A node of a linked data structure generally contains two pieces of information — a reference to the actual data being stored and a reference to the next node on the list. A linked list is traversed, or searched, by stepping through each of the data nodes, beginning at the first one, or the head of the list. There is no way to find information in a linked list without sequentially moving through the nodes from beginning to end.
Most linked data structures will use as little memory as possible during program execution. If a linked list is created with only one node and no other nodes are added, that list will take up the memory required for only one node. This is in stark contrast to an array data structure in which the size of the entire array must be declared and allocated at the start of the program and cannot be changed.
Linked lists pay for their efficient use of memory resources by requiring more computing power. Finding a specific piece of data in a linked list requires looping through the entire list every time, so it can be slower to access information in the middle of the list. Removing or reordering data in a linked list also can be more computationally intensive than managing an array in which elements can be swapped easily.
A linked data structure is not required to have only one reference to the next node; it can have several. Some linked lists have two node references, one to the next node in the list and one to the previous node. These are known as doubly linked lists. This can make moving through a list in either direction much faster, though at the expense of increased memory usage for the data structure.
It is possible for linked lists to have three or more references to other nodes in the list. This creates a structure similar to a tree with entire branches of nodes spawning from a single one. These types of data structures are called multiply linked lists. Multiply linked lists are particularly useful for complex sorting algorithms that are used to structure data. Search trees are possible largely because of the use of linked data structures to create multiple, variable-length branches.