Linked Structures

Linked lists are made up of nodes, where each node contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo.

A linked list is considered a recursive data structure because it has a recursive definition.

A linked list is either:

1. the empty list, represented by None, or
2. a node that contains a cargo object and a reference to a linked list.

i.e. sequence of nodes, each with a value and reference to next node.(Use 'next'?)

e.g.

class Node:
    def __init__(self, cargo=None, next=None):
        self.cargo = cargo
        self.next  = next

    def __str__(self):
        return str(self.cargo)

 

24.11. Glossary

embedded reference

A reference stored in an attribute of an object.

linked list

A data structure that implements a collection using a sequence of linked nodes.

node

An element of a list, usually implemented as an object that contains a reference to another object of the same type.

cargo

An item of data contained in a node.

link

An embedded reference used to link one object to another.

precondition

An assertion that must be true in order for a method to work correctly.

fundamental ambiguity theorem

A reference to a list node can be treated as a single object or as the first in a list of nodes.

singleton

A linked list with a single node.

wrapper

A method that acts as a middleman between a caller and a helper method, often making the method easier or less error-prone to invoke.

helper

A method that is not invoked directly by a caller but is used by another method to perform part of an operation.

invariant

An assertion that should be true of an object at all times (except perhaps while the object is being modified).