10. Links
Note
This topic is not introducing a ADT. Instead, it is introducing the idea of linked structures. These linked structures may be used to implement ADTs
Arrays have a fixed size
But the
expandCapacitytrick can hide this
When using an array, data may need to be shifted around when adding and/or removing
Traditionally speaking, arrays are in contiguous memory addresses
The successor value is in the next array cell
JVM asterisk — In Java, arrays are objects, and objects go into the heap, which isn’t necessarily contiguous
10.1. Linked Structure
A linked data structure is one that consists of objects referencing other objects
Example linked structure consisting of five “nodes”. Note that “head” is not a node, but a reference to a node.
Linked structures do not have a fixed size
With this linking idea, data does not need to be stored in consecutive memory locations
Successors can be anywhere
Data can be inserted and removed by updating the references/links
No need to shift data around
10.2. Nodes
A node is a basic unit in the linked structures
For the following examples, the focus is on singly linked structures
Each node has only one link
The series of nodes linked together is what makes up the singly linked structure
The nodes link to their successor nodes
Example single node containing a reference to some data and a reference to a successor/next node. These references may refer to null.
A node for a singly linked structure typically has two fields
data — a reference to the data to be stored
To compare to the array, this would be the data put into the cells of the array
next — a reference to the successor/next node
Arrays don’t have this because the successor is just in the next cell in the array
10.3. Inserting into a Linked Structure
Example of a singly linked structure. Note that “head” is not a node, but a reference to a node.
With a reference to the head of the linked structure and the two fields (
dataandnext) of the node classHow would one access the first node’s data?
How would one access the second node’s data?
How would one access an arbitrary node’s data?
How would you access the predecessor?
How would we add something to the front of this linked structure?
How would we add something to the middle of this linked structure?
How would we add something to the end of this linked structure?
How would we remove something to the front of this linked structure?
How would we remove something to the middle of this linked structure?
How would we remove something to the end of this linked structure?
10.3.1. Adding to the Front
Given a reference to the front of the linked structure (
head) and a reference to the node to be inserted (node)
Have the node to be inserted’s
nextreference the node referenced byhead
Have
headreference the new node, which is the new front of the linked structure
The new node is now at the front of the linked structure
10.3.2. Adding to the Middle
Given a reference to the front of the linked structure (
head) and a reference to the node to be inserted (node)
Locate the node the new node will be inserted after
In this example,
currentis a reference to the node the new node will be inserted after
Have the new node’s
nextreference its soon to be predecessor’s (current)nextThis is the node that the node being inserted will come before
Update the predecessor’s (
current)nextto reference the new node being inserted
The new node is now at the desired location
10.3.3. Adding to the End
Adding to the middle is a more general case compared to adding to the front
Adding to the front is a special case
The process to add to the end of a linked structure is the same as adding to the middle
The difference is that the predecessor’s next will have been
null, but this does not change the algorithm
10.4. Removing from a Linked Structure
10.4.1. Remove from the Front
Removing from the front may be the easiest operation
Given a reference to the front of the linked structure (
head)
Update
head, the reference to the front of the linked structure, to refer to the current front’snext
With no reference to the old front, it is effectively removed from the linked structure
10.4.2. Remove from the Middle
Given a reference to the front of the linked structure (
head)Locate the node to be removed (
current) and the node immediately before it (previous)
Have the predecessor’s (
previous)nextrefer to the node being removed’s (current)next
There is now no way to access the removed node from the linked structure
10.4.3. Remove from the End
Like adding to the end of a linked structure, the process of removing from the end is the same as removing from the middle
10.5. Node Implementation
Remember, reference variables contain a reference to an object
The linked structure uses these references to link the structure together
The node implementation for the singly linked structure is kept simple
A field to keep track of the data
A field to keep track of the next/successor node
Constructors
Getters and setters
1/**
2 * A node class for a singly linked structure. Each node contains a nullable reference to data of type T, and a
3 * reference to the next/subsequent/successor singly linked node, which may be a null reference.
4 *
5 * @param <T> Type of the data being stored in the node
6 */
7public class Node<T> {
8
9 private T data;
10 private Node<T> next;
11
12 public Node() {
13 this(null);
14 }
15
16 public Node(T data) {
17 this.data = data;
18 this.next = null;
19 }
20
21 public T getData() {
22 return data;
23 }
24
25 public void setData(T data) {
26 this.data = data;
27 }
28
29 public Node<T> getNext() {
30 return next;
31 }
32
33 public void setNext(Node<T> next) {
34 this.next = next;
35 }
36}
10.5.1. Explore the Implementation
1public class PlayingLinks {
2 public static void main(String[] args) {
3 // Create a Node
4 Node<Integer> head = new Node<>(0);
5 System.out.println(head.getData());
6
7 // Make a linked structure of the numbers 0 -- 9
8 Node<Integer> currentNode = head;
9 Node<Integer> newNode;
10
11 for (int i = 1; i < 10; i++) {
12 newNode = new Node<>(i);
13 currentNode.setNext(newNode);
14 currentNode = currentNode.getNext();
15 }
16
17 // Print the contents of the linked structure
18 currentNode = head;
19 while (currentNode!= null) {
20 System.out.println(currentNode.getData());
21 currentNode = currentNode.getNext();
22 }
23
24 // Try adding to the front, middle, and end of the structure
25
26 // Try removing from the front, middle, and end of the structure
27
28 }
29}
Warning
As previously mentioned, head is not a node; head is a reference to a node. For example,
head = someNode; and head.setNext(someNode); have two very different meanings. The first means that the
node reference variable head will refer to the node someNode, while the second means that the node
referenced by head's next node reference will refer to someNode.
Result of head = someNode;. The reference variable head is updated to reference the node also referenced
by the reference variable someNode.
Result of head.setNext(someNode);. The node referenced by head is updated such that it’s next field
refers to the node also referenced by the reference variable someNode.
10.6. Variations
Like most things learned in this course, there are variations for nodes
One may be wondering: Can nodes have references to their predecessors too?
Absolutely
10.6.1. Doubly Linked
An example of a doubly linked structure. In addition to the data and next field, each node also has a field
to access its predecessor. This particular example includes reference variables for the front (head) and end
(tail) of the linked structure.
How would the
Nodeimplementation need to change to facilitate this?
10.7. For Next Time
Read Chapter 4 Sections 1 – 3
7 pages
10.7.1. Playing Code
Try writing code to add/remove from the front/middle/end of the linked structure
Download and play with