CP164 Study Guide - Final Guide: Linked Data, Init
Linked Data Structures
So far we have worked with array-based data structures. Our stacks, queues, and priority queues
have been implemented with the Python list that allows us to access individual elements with an
index value. However, these data structures can also be built upon linked data elements rather
than indexed data elements. We can add and delete these linked data elements as required and so
replicate the methods of the array-based data structures. We will also discover that implementing
non-linear data structures, such as trees, is actually easier to do with a linked structure than with
an array-based structure.
Linked data structures are based upon nodes. A node typically consists of two parts:
• a data part, which may contain any kind of value
• at least one pointer, or link, part, which links to another node
A Single-Linked Node
A data structure is built by linking together a series of these nodes. How they are linked together
determines the type of data structure that is built. We will look at a linked Stack data structure in
order to understand such a structure is built.
The Linked Stack Implementation
Implementing the Linked Stack
A linked stack has the values 7, 5, 3, and 1 pushed onto it. The resulting nodes look like this:
A Simple Linked Stack
Remember that a node contains a single value and a link to the next node:
A Single-Linked Node
How, then, can we construct a stack from these individual nodes? How can we link the
nodes together? How can we define such a node in Python?
The _StackNode Class
A stack node is very simple: it needs only a _data attribute and a _next attribute. A node is
created only when there is a value to add to the stack. There is no use for an empty node.
The _StackNode constructor takes care of that. Other than the constructor,
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
So far we have worked with array-based data structures. Our stacks, queues, and priority queues have been implemented with the python list that allows us to access individual elements with an index value. However, these data structures can also be built upon linked data elements rather than indexed data elements. We can add and delete these linked data elements as required and so replicate the methods of the array-based data structures. We will also discover that implementing non-linear data structures, such as trees, is actually easier to do with a linked structure than with an array-based structure. A node typically consists of two parts: a data part, which may contain any kind of value at least one pointer, or link, part, which links to another node. A data structure is built by linking together a series of these nodes. How they are linked together determines the type of data structure that is built.
