What Is a Linked Data Structure?

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.