Linked-List Data Structure

A linked-list is a sequential data structure implemented as linked nodes. Each node typically contains one or more values and one or more links to neighboring nodes. The term link means pointers pointing from one node to another.

digraph ll { rankdir=LR; node [shape=record]; head [label="head"]; a [label="{ <data> 12 | <ref> }", width=1.2]; b [label="{ <data> 99 | <ref> }"]; c [label="{ <data> 37 | <ref> }"]; head:e -> a:data [arrowhead=vee, arrowtail=none, dir=both, tailclip=false]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; }

a minimal linked-list

Characteristics

  • A data structure based on linked nodes

  • Nodes are linked together by links

  • Logically contiguous, physically non-contiguous

  • Advantages

    • Dynamic size

    • Ease of insertion/deletion

    • Not requiring contiguous memory

    • Sequential access

  • Limitations

    • Inefficient random access

    • Extra memory space

Implementation Variations

  • Minimal implementation: a head pointer; singly-linked

  • Ideal implementation: a head pointer, a tail pointer; a size/count instance variable; doubly-linked

  • Reference pointers

    • head pointer

    • tail pointer

  • Number of links per node

    • singly-linked - a pointer to next node

    • doubly-linked - pointers to previous and next nodes

  • Terminal node handling (FYI)

    • cyclic - link(s) connecting the first and last nodes; not useful

    • acyclic

  • Dummy node before the first node (FYI)

    • simplifies empty list and first node handling

    • complicates other operations

    • not useful

Behaviors

  • Insertion

    • at the beginning

    • at the end

    • at a specified position (by value, by index)

  • Removal

    • at the beginning

    • at the end

    • at a specified position (by value, by index)

C++ Implementation Details

  • Classes

    • linked-list class

      • head pointer

      • tail pointer

      • size/count instance variable

    • node class/struct

      • Option 1: top-level class, not nested (preferred most of the time)

      • Option 2: nested class/struct (better information hiding)

  • Use class templates for generalization

    • type of data stored in nodes can be parameterized

    • make a header only module

  • Insert before a given node

    • cannot handle insertion after the last node

  • Append

  • Remove

Time Complexity

  • Based on the Ideal Implementation (head pointer, tail pointer, size/count instance variable; doubly-linked)

  • Search by value \(\Theta(n)\)

  • Indexing (access kth element) \(\Theta(n)\)

  • Insert \(\Theta(1)\) (\(\Theta(n)\) if locate the insertion point first)

  • Remove \(\Theta(1)\) (\(\Theta(n)\) if locate the removal point first)

Pitfalls

  • Linked-List is not an ADT. It is a data structure to be used to implement some ADTs.

  • Not handling empty list

  • Not handling the first/last element

Linked-list Glossary

Linked-List

A sequential data structure based on linked nodes

A pointer pointing to node

Node (linked-list)

The base unit linked together to form a linked-list

Dummy Node (linked-list)

The empty node added in front of the first node to simplify certain linked-list algorithms