Linked list

As explained in Elixir in Action, Third Edition

A singly linked list is a sequence of nodes in which each node refers to the next node and traversal proceeds in one direction.

A singly linked list is a sequence of nodes, where each node contains a value and refers to the next node. Elixir lists use this recursive structure, so traversal proceeds from the head toward the tail. section 2.4.4

The representation makes some operations natural and others expensive:

• Prepending uses the cons form [head | tail] and adds an element without traversing the existing list. section 2.4.4
• Finding an element, calculating length, accessing by index, replacing, inserting, appending, and concatenating generally require traversal and have O(n) complexity. section 2.4.4
• Choose tuples, maps, or a higher-level data structure when direct access is required. section 2.4.4

Decomposing and extending a list

Pattern matching exposes the first element and the remainder: a_list = [head | tail]. The same structure supports construction, as in [:new_element | a_list], which prepends without mutating the original binding.

Figure 2.1 Recursive structure of the list [1, 2, 3, 4]

View the recursive structure of [1, 2, 3, 4] as nested head-and-tail links. section 2.4.4

How Elixir in Action, Third Edition covers it

How deep it goes

Explains recursive representation, construction, traversal costs, and operation trade-offs, while deferring detailed List-module reference.

Examples

Demonstrates prime-number lists, indexed access, membership, replacement, insertion, concatenation, and head-tail decomposition.

What you can do after

Apply it via List and Enum operations while recognizing when sequential access makes another data structure more suitable.

How it connects

Connects lists with arrays, tuples, maps, enumerables, and the List and Enum modules.

liveBookmanning.com

Read Elixir in Action, Third Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Grokking Data StructuresA linked list is a collection of nodes connected by links, allowing elements to be inserted or removed without requiring contiguous storage.
• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionA linked list is an ordered data structure whose items store links to the addresses of subsequent items rather than occupying adjacent memory locations.
• 

  liveBookmanning.com
  Fabulous Adventures in Data Structures and AlgorithmsA linked list is a sequence of nodes in which each node refers to the next node in the sequence.
• 

  liveBookmanning.com
  Julia as a Second LanguageA linked list is a collection data structure whose elements are connected through links rather than stored in one contiguous indexed sequence.
• 

  liveBookmanning.com
  Go in Action, Second EditionA linked list is a sequence data structure whose elements are stored in nodes connected by links and whose element type can be parameterized in its generic form.
• 

  liveBookmanning.com
  Functional Programming in Scala, Second EditionA singly linked list is a sequence represented by nodes in which each nonempty node contains an element and a reference to the remaining list.
• 

  liveBookmanning.com
  AI-Powered Developer: Build software with ChatGPT and CopilotA linear data structure whose elements are connected through links or references to other elements.

Compare how 8 books explain linked list →

Related concepts

• doubly linked listincludes · A doubly linked list is a linked sequence in which each node has references to both its predecessor and successor.
• listincludes · A list is an ordered collection of elements arranged in a sequence.
• containerkind of · A container is a structure or entity that holds, groups, or packages other data or elements.
• data localitycontrasts with · Data locality describes the relationship between where data is located and where or how it is accessed or processed, including proximity, reuse, and location constraints.
• sequential accessuses · Sequential access is a data-access pattern that retrieves elements or records in an ordered sequence, typically beginning at the first element or location.

This explainer was generated by Manning's knowledge graph from the text of Elixir in Action, Third Edition. The section links point to the parts of the book it draws on.