Data Structures and Algorithms
Primary version
Primary version
  • Data Structures and Algorithms
  • Algorithms Analysis
    • Measuring Resource Consumption
    • Growth Rates
    • Asymptotic Notation
    • Analysis of Linear Search
    • Analysis of Binary Search
    • How to do an analysis in 5 steps
  • Recursion
    • Writing a recursive function
    • How do recursive functions work?
    • Analysis of a Recursive Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Concepts
      • Implementation - List and Nodes
      • Implementation - push_front(), pop_front()
      • Implementation - Iterators
      • Modification - Sentinel Nodes
  • Stacks and Queues
    • Stack Implementation
    • Queue Implementation
  • Table
    • A Simple Implementation
    • Hash Tables
      • Bucketing
      • Chaining
      • Linear Probing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
    • Quick Sort
    • Heap and Heap Sort
      • Priority Queues using Binary Heaps
      • Heapify and Heap Sort
  • Trees
    • Binary Trees
    • Binary Search Trees
    • BST Implemenation
    • Iterative Methods
    • Recursive Methods
  • AVL Trees
  • Red Black Trees
  • 2-3 Trees
  • Graphs
  • Introduction to Computational Theory
  • Appendix: Markdown
  • Appendix: Mathematics Review
Powered by GitBook
On this page
  • Introduction
  • Typical Operations
  • Enhancements
  1. Lists

Linked List

PreviousImplementationNextConcepts

Last updated 6 years ago

Introduction

A linked list is a data structure that stores a collection of objects in a sequential manner. Each item in list is stored in a node. Each node consists of a single piece of data (it is permissible for the data to be an aggregate type) along with at least one pointer to another node, typically the next node within the list. The linked list object itself must contain a pointer to a node within the list that will allow access to every other node by following the pointers in the node. Usually this is a pointer to the first node in the linked list.

If you wanted to store an array of 5 numbers in an array this is what the array would look like:

A simple linked list that stores the same 5 numbers in the same sequence would look like this

The above is a singly linked list. It is called this because there is a single pointer out of each node to another node.

Note that while the above diagram only has a single pointer out of the linked list object itself, it is not part of the definition of a singly linked list. The single link only refers to the link from one node to another

Typical Operations

To look at how to implement a linked list, the operations a linked list can do should be considered. A linked list can typically support some subset of the following operations.

  • push_front - add an item to the front of the linked list

  • push_back - add an item to the back of the linked list

  • pop_front - remove the frontmost item from the linked list

  • pop_back - remove the backmost item from the linked list

  • insert - given a point within the list insert an item just before that point

  • erase - remove a node at a specific point within the list

  • erase(a,b) - erases all nodes between a and b

  • traversals - some operation that applies to every node in the list

Enhancements

To support the above operations, a linked list typically will store more information than the basic list. We will detail these in the implementation section

array of 5 floats