CIS 3130 Lecture 05 — Nodes &Linked Lists

CIS 3130
Data Structures
Lecture 08
Linked Implementations

Motivation

Ring buffers get us all the way to efficient implementations of deques
- stacks and FIFO queues can be efficiently implemented leveraging the deque
- alternatively the stack can be independently implemented with a 'tos' (top-of-stack) index variable
- there's no real reason to independently implement a FIFO queue
  - the efficient independent implementation was using a ring buffer anyway

However, lists provide insertions/deletions inside the sequence, seemingly requiring shifts. This can be avoided by switching from the contiguous storage scheme of the array to a linked representation.

Implicit vs Explicit Addressing

Arrays use implicit addressing:

Address of an element is implicit — a function of how far it is from the beginning of the array
- the index is not actually stored anywhere; rather it is calculated
This is a direct consequence of the array being contiguous

This is in contrast with explicit addressing … stored with each element of the sequence is the location of the next element.

You've seen explicit addressing in Java; it is used in the context of reference variables and objects: the variable contains an explicit reference to the object it is referencing
- The compiler hides the details of going from the reference to the object, but the reference is there … explicitly stored in the reference variable's location

Nodes: The Atoms of Linked Implementations

In a linked implementation, the elements are maintained in a sequence where the order is maintained by explicit addresses, usually called links or pointers. Each element is stored in a discrete entity known as a node or cell containing:

the data for that element
an link to the next element in the sequence
possibly additional links

Nodes in Java

class Node<E> {
	Node(E data) {this(data, null);}
	Node(E data, Node next) {
		this.data = data;
		this.next = next;
	}
	E data;
	Node next;
}

There are a couple of operations that can be coded using nothing more than the notion of a node (i.e., before moving on to lists of nodes).

Operations Involving a Specified Node

`insertAfter`

Insert an element after a particular node (pointed to by the node parameter)

void insertAfter(Node node, E data) {
	if (node == null) throw new Exception("...");
	Node newNode = new Node(data, node.next);
	node.next = newNode;
}

Ensure the operation is valid
Get a new node

Initialize the new node's data field to the passed data

	Copy node's next field to the new node's next field
	
Set node's next field to the new node.

`removeAfter`

Remove the element after a particular node (pointed to by node) in a list

E removeAfter(Node node) {
	if (node == null) throw new Exception("null sent as argument to removeAfter");
	if (node.next == null) throw new Exception("Attempt to remove node after last node of list");
	Node hold = node.next;
	node.next = hold.next;
	return hold.data;
}

Ensure the operation is valid
Save the pointer to the node to be deleted
Point node's next field to the node after the node to be deleted
return the data from the removed node

Notes

The above operations assume we already have a pointer (reference) to the node passed in as the parameter (i.e., the node after which we are performing the insertion or the node immediately in front of the node to be deleted).
Notice that we can't do insert a new node before the specified node, nor can we delete the node before this node (or the node itself) because of the lack of a pointer in that direction

Lists of Nodes — Linked Lists

Nodes can be linked together into sequences/lists via their next link fields; the result as known as a linked list
In order to access the list, we maintain an external pointer — usually named head — to the first node on the list.
- Other external pointers may be used as well, to facilitate the operations on the list
The other nodes on the list are reached via traversing sequentially along the internal pointer fields maintained in the next explicit address fields of the nodes.
The last node on the list contains null in its next field to indicate the end of the list
Initially, we'll examine lists of nodes containing a single next link/field; we call these singly-linked lists

Advantages of Linked Lists

No shifting; instead, links will be manipulated
no capacity issues; nodes are allocated as needed

Disadvantages of Linked Lists

no true random access; accessing the n'th element involves a O(n) sequential/linear traverse though the list
- for example, even if the list was sorted, binary search wouldn't help much; just getting to the middle element would require a linear traversal
constantly allocating small amounts of memory … can get expensive
- one way of getting around this is to preallocate a node pool; but this then leads back to capacity issues, i.e., what happens when you run out of nodes in the pool
nodes can be scattered all over memory; can wreak havoc with operating system memory placement policies

Linked list wikipedia entry

Linked Lists in Java

class LinkedList {
	Node head = null;
}

The external reference to the list is maintained as an instance variable of the container class.

Some Tips on Working with Linked Lists

Pay attention to the initial state
Be aware of the physical vs logical container
Pay attention to inserting from an empty list (going from empty to non-empty)
Pay attention to removing a singleton element (going from non-empty to empty)
Pay attention to operations that may operate at the ends of the list
Give every node a name; e.g., don't work on node.next

A Progression of Linked Lists

Singly-linked Linear (SL1N — Singly-linked / Linear / 1 pointer / No header

Provides direct access to first node on list

Notes

We display the non-empty state first, it motivates the empty state
- For this first, simple example it's not really necessary, but it becomes useful later as the linked lists grow in sophistication
- We did something similar when 'reverse-engineering' the double pointer FIFO queue by looking at the list of size 1 and then seeing what happens when we remove the single element, leaving an empty list

public class SL1N_Deque<E> implements Deque<E>{
	static class Node<E> {
		public Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
		Node(E data) {this(data, null);}
		Node() {this(null);}

		E data;
		Node<E> next;
	}

	public void addFirst(E data) {
		var node = new Node<>(data, head);
		head = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = head;
		head = head.next;
		return node.data;
	}

	public void addLast(E data) {
		if (isEmpty()) 
			addFirst(data);
		else {
			Node<E> p = head;
			while (p.next != null) {
				p = p.next;
			}
			p.next = new Node<E>(data);
		}
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		Node<E> p = head;
		while (p != null) {
			count++;
			p = p.next;
		}
		return count;
	}

	public boolean isEmpty() {return head == null;}

	public String toString() {
		String result = "{";
		var p = head;
		while (p != null) {
			result += p.data + (p.next != null ? ", " : "");
			p = p.next;
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> head = null;
}

Notes

Each of the implementations will have their code presented, with the exception of the removeLast method which is left as a lab.
We will use an inner class for the Node class
- In general, the linked list class is the only one to use its nodes, so it makes sense to hide this class
- There are also two different sorts of nodes; keeping them out of sight in the class that uses them keeps things cleaner
addFirstr and removeFirst simply manipulate pointers, they do not traverse the list or otherwise do anything that is proportional to the size of the list, and thus they are O(1) operations.
addLast and removeLast both require a traversal to the end of the list in this implementation, thus making them O(n) operations.
The addLast method leverages the addFirst when the list is empty (i.e., when adding the last element is the same as adding the first element).
```
if (isEmpty()) 
	addFirst(data);
		
```
- This is more than simply a matter of leveraging, i.e., special logic is required form addLast when the list is empty.
  - As discussed, addLast involves a traversal to the end of the list. Here is that logic:
```
>
Node<E> p = head;
while (p.next != null) {
	p = p.next;
}
p.next = new Node<E>(data);
						
```
  - If the list is empty this code would fail with a NullPointerException in the while header:
```
Node<E> p = head; 	// if list is empty, p == head == null
while (p.next != null) {
p = p.next;
}
						
```
  - To properly handle the case of empty (without the leveraging we did), one would have to use a technique known as piggybacking in which a second pointer (q) trails one node behind p, and thus remins on the end o fhte list when p falls off (p == null (more on piggybacking below):
```
// without leveraging addFirst
public void addLast(E data) {
	Node<E> p = head q = null;
	while (p != null) {
		q = p;
		p = p.next;
	}
	if (q == null) 			// q never moved; list was empty
		head = new Node<E>(data);	// or could have called addFirst
	else
		q.next = new Node<E>(data);
}
						
```
  - Leveraging addFirst somewhat hides this issue, but it still required us to test oofr this condition (if isEmpty())
- This also applies to removeLast for a singleton (i.e., one -element) list … removing the last element is the same as removing the first element.
size also requires a traversal, making it an O(n) operation
- This is especial onerous if one was to use a for loop of the form:
```
for (int i = 0; i < list.size(); i++)
				
```
  which then actually becomes a O(n²) operations (n times through the loop — O(n) — with the call to size itself being O(n).
Notice the code for isEmpty: head == null, rather than size() == 0.
- isEmpty / size is the 'poster child' of method leveraging. In general, isEmpty is defined as size() == 0:
  - This allows one to leverage the logic of the size method in order to come up with a succinct, readable definition of isEmpty and thus allows us to avoidm replicating that logic in isEmpty
  - It also allows one to actually implement isEmpty in an abstract class, where the definition (implementation) of size is deferred to a subclass.
- In this implementation however, using size to define isEmpty transforms an O(1) operation (head == null) into an O(n) (as discussed above, size is an O(n) operation in this implementation.
- One could maintain a size instance variable in the list to avoid the traversal, which would solve both problems (the overhead of using size n the for loop and using it to leverage isEMpty
  - Of course, that introduces the overhead (both performance and code maintenance) of maintaining the size variable
- The takeaway is that one should at least be cognizant that leveraging can have a downside; i.e., employing a fairly expensive operation to define one that could be done in a far more efficient manner.
The capacity method which had discussed earlier as not being part of the 'pure' interface (being an implementation issue) becomes a bit of an issue here, since indeed, linked lists do not have a capacity issue.
- However, as also discussed earlier, it is used (at least in the context of this course) to be able to have some information about the capacity from the outside (for debugging, testing, and illustration purposes.
- We thus return a -1 as the capacity value of our list, thus allowing us to conform to our 'capacity'-possessing interface, but specifying an 'impossible' capacity, thus informing the call that there is no capacity information wrt the list.
- JCF does something similar in that it has various 'Optional' operations that may be useful / implementable under certain implementations, but not under others. By convention, calling such an operation from an implementing class that does NOT supply it causes an UnsupportedOperationException to be thrown.

initial state

head == null

Efficient operations

insertion/removal at head (front)
insertion/removal after a specified node
- getting to that node is a different story

Requires traversal

insertion/removal at tail (rear)
insertion/removal before/after a specified node

'Random access' of nodes

traversal
- although the List interface supports get/set methods, those operations require a traversal in a linked implementation, making them O(n)
piggybacking
- operating on a specific node (for example deleting a node with a specified value, or deleintg the i'th node), requires stopping at the node before the specified node (because of the on-way nature of the linkes.
  - This is accomplished though a technique known as piggybacking, maintaining two node references, one that traverses the list (looking for the specified node); the other staying one node back.
  - Examples will foll in subsequent implementations
Node getNodeAt(int position)
- if one is implementing a List using these implementation (i.e., where getting to a node requires a traversal), it is useful to introduce a helper method, getNodeAt(int i) that returns a reference to the i'th node and either null or throws an exception if i is beyond the end of the list (or negative).
maintaining size field
- as discussed above, this can be useful; it is also useful in the context of the getNodeAt method to check that i is in the bounds of the list before embarking on what could be an expensive traversal if the list is large.

Good for implementing

Stack (head replaced with tos)

One could either use composition and leverage the addFirst and removeFirst methods (renaming them push and pop, or alternatively code the Stack directly (i.e., independently).

Stack implementation Using a Singly Linked Linear List

`push`

Inserts an element at the front of the linked list

void push(int data) {		// same as an addFront method
	Node  node = new Node(data, head); 
	head = node;
}

Get a new node
- Initialize the new node's data field to the passed data
- Initialize the new node's next field to the current head of the list
- this could have also been accomplished using the one-argument constructor (clearer?)
```
Node node - new Node(data);
node.next = head;
				
```
Point the head of the list to the new node

More succinctly:

void push(Node *&head, const EType &data) {
	head = new Node(data, head);
}

`pop`

Remove and return the element from the front of the linked list

int pop() {									// same as a removeFront method
	if (isEmpty()) throw new Exception("....");
	Node hold = head;
	head = head.next;
	return hold.data;
}

Ensure the operation is valid
Save a pointer to the first node (the one to be deleted)
Point the head of the list the node after the node to be deleted
return the data field of the removed node

If one coded an independent implementation (i.e., this means creating a stack class with the above methods and a tos instance variable — as opposed to leveraging SL1N — there would be no need for addLast / removeLast, and thus the whole issue of special logic (which was only applicable when operating at the end of the list) goes away.

Other Comments

Notice that for an array, the efficient operations are at the end of the array, for our singly linked linear list, they're at the beginning of the list
Can't use the above list type for a FIFO queue (and definitely not a deque without having to perform traversals to the other end of the list
We'll have a better representation for the general list container, so there really is no reason to implement any other operations (i.e., the insert-after and remove-after)

Header (Dummy) Nodes

For 'Meta' Data (Historical)

There is a technique to add an additional 'meta'-node to the beginning of the list that contains meta-information about the list; e.g. number of nodes (to avoid traversal when implementing a 'length' method), or maximum value in the list, etc.

this would typically require a different node structure (i.e., the data filed would be different) than that of the rest of the list and would probably require the introduction of a hierarchy to accomodate both the 'normal' data nodes and the 'meta'-node
```
class Node {
	Node next;
}

class DataNode extends Node {
	private E data;
}

class MetaNode implements Node {
	MetaData data;
}

class LinkedList {
	MetaNode head;
}
```

This made sense back before structures and classes were common if existent, and this was a way of 'bundling' a piece of meta-data into the structure. Once a heterogeneous structure (i.e., the list field and the m,etadata field) could be defined together, this technique became obsolete.
The resulting coding is also quite cumbersome, particular since this was applicable before object-oriented languages were mainstream, and thus inheritance could not be used. The 'old' way of doing it was quite opaque and resulted in some typically error-prone approaches.

To Eliminate Special Logic (Current)

Having a header node always present on the list avoids the special logic of updating 'head' during the empty → non-empty and non-empty → empty transitions.

A hierarchy is unnecessary as the header node has the same type as the rest of the nodes

Singly-linked Linear With Header Node (SL1H — Singly-linked / Linear / 1 pointer / Header

Simplifies insertion/removal logic, by eliminating the special cases of empty → non-empty and non-empty → empty transitions.

public class SL1H_Deque<E> implements Deque<E>{
	static class Node<E> {
		public Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
		Node(E data) {this(data, null);}
		Node() {this(null);}

		E data;
		Node<E> next;
	}

	SL1H_Deque() {
		header = new Node<>();
	}

	public void addFirst(E data) {
		var node = new Node<>(data, header.next);
		header.next = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = header.next;
		header.next = node.next;
		return node.data;
	}

	p ublic void addLast(E data) {
		Node<E> p = header;
		while (p.next != null) {
			p = p.next;
		}
		p.next = new Node<E>(data);
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		Node<E> p = header.next<.span>;<.span>
		while (p != null) {
			count++;
			p = p.next;
		}
		return count;
	}

	public boolean isEmpty() {return header.next == null;}

	public String toString() {
		String result = "{";
		var p = header.next;
		while (p != null) {
			result += p.data + (p.next != null ? ", " : "");
			p = p.next;
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> header = null;
}

Notes

The constructor creates a header node and points head to it.
The empty condition is now if the header node is the only node on thelist
To start traversing the list, the traversing pointer (typically p is set to refer to the node pointed to by the header node.
Note the absence of any special logic for addLast; p is set to the header node, which is always there and thus the p.next is completely safe.

initial state

head = header-node

Efficient operations

insertion/removal at head (front)
insertion/removal after a specified node
- getting to that node is a different story

Requires traversal

insertion/removal at tail (rear)
insertion/removal before/after a specified node

Good for implementing

As mentioned above, an independent (i.e., direct) implementation of a stack need not include addFirst or removeFirst, and thus there is no benefit to having a header node in that context; the special logic only is required when operating at the end of the list, and stack operates only at the beginning.

Singly-linked Linear With Head and Tail Pointers (SL2N — Singly-linked / Linear / 2 pointers / No header

Provides direct access to first and last node on list

mublic class SL2N_Deque<E> implements Deque<E>{
	static class Node<E> {
		public Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
		Node(E data) {this(data, null);}
		Node() {this(null);}

		E data;
		Node<E> next;
	}

	public void addFirst(E data) {
		var node = new Node<>(data, head);
		if (head == null) tail = node;
		head = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = head;
		head = head.next;
		if (head == null) tail = null;
		return node.data;
	}

	public void addLast(E data) {
		if (isEmpty()) 
			addFirst(data);
		else {
			Node<E> node = new Node<E>(data);
			tail.next = node;
			tail = node; 
		}
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		Node<E> p = head, q = null;
		while (p != null) {
			count++;
			q = p;
			p = p.next;
		}
		if (q != tail) {
			System.out.println("*** Deque integrity error: tail is not pointing at last node");
			System.exit(1);
		}
		return count;
	}

	public boolean isEmpty() {return head == null && tail == null;}

	public String toString() {
		String result = "{";
		Node<E> p = head, q = null;
		while (p != null) {
			result += p.data + (p.next != null ? ", " : "");
			q = p;
			p = p.next;
		}
		if (q != tail) {
			System.out.println("*** Deque integrity error: tail is not pointing at last node");
			System.exit(1);
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> 
		head = null, 
		tail = null;
}

Notes

With the introduction of the tail pointer, addLast becomes an O(1) operation.
- removeLast (which you are to code), however, remains an O(n) as it requires a traversal to get to the node before the one pointed to by tail.
- We thus have 3 of the 4 insert/remove operations being O(1). This will allow us to define an efficient FIFO queue using this list implementation.
- But deque still eludes us
Note in addFirst and removeFirst, we have special logic assigning dealing withthe synchronization of tail
- Neither of these operations should involve tail being at the front of the list
  - However, when the list is empty or consists of a single element, the front of the list is also the back of the list and thus tail will be affected as well.
  - For insertion into an empty last, tail (which, like head, was null needs to be assigned to the node.
  - Similarly for removal of a singleton element (the one element of single-element list), tail must be set to null (in addition to head being set to null as part of the removeFromt code.
While a header node might eliminated the special logic in the addLast/removeLast methoids, it doesn't address the special logic of keeping the two pointers in synch.

initial state

head == tail == null

Efficient operations

insertion/removal at head
insertion at tail
insertion/removal after a specified node
- getting to that node is a different story

Requires traversal

removal at tail
insertion/removal before a specified node

As discussed above, this implementation requires special-case logic in order to synch the two pointers wrt empty → non-empty and non-empty → empty transitions

insertions typically involve tail only
- insertion into an empty list requires head to be updated as well
removals involve head only
- removal of single node causing list to go empty requires tail be updated as well

Good for implementing

FIFO queue

FIFO Queue Implementation Using Singly Linked Linear List with Head and Tail Pointers

Again, we could leverage this implementation to create a FIFO queue class, or directly implement the methods (as follows)

`add (to rear)`

void add(E data) {
	Node node = new Node(data);
	if (tail != null)
		tail.next = node;
	else
		head = node;
	tail =  node;	
}

`remove (from front)`

E remove() {
	if (isEmpty()) throw new Exception("…");
	E data = head.data;
	head = head.next;
	if (head == null) tail = null;
	return data;;
}

Singly-linked Circular with Single Pointer to 'Last' Node on List (SC1N — Singly-linked / Circular / 1 pointer / No header

Provides direct access to last and first node on list using a single tail pointer

public class SC1N_Deque<E> implements Deque<E>{
	static class Node<E> {
		public Node(E data, Node<E> next) {
			this.data = data;
			this.next = next;
		}
		Node(E data) {this(data, null);}
		Node() {this(null);}

		E data;
		Node<E> next;
	}

	public void addFirst(E data) {
		var node = new Node<>(data);
		if (tail == null) {
			node.next = node;
			tail = node;
		}
		else {
			node.next = tail.next;
			tail.next = node;
		}
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = tail.next;
		if (tail.next == tail) 
			tail = null;
		else
			tail.next = node.next;
		return node.data;
	}

	public void addLast(E data) {
		addFirst(data);
		tail = tail.next;
		
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		if (tail != null) {
			Node<E> p = tail.next;
			do {
				count++;
				p = p.next;
			} while (p != tail.next);
		}
		return count;
	}

	public boolean isEmpty() {return tail == null;}

	public String toString() {
		String result = "{";
		if (tail != null) {
			var p = tail.next;
			do {
				result += p.data + (p.next != tail.next ? ", " : "");
				p = p.next;
			} while (p != tail.next);
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> tail = null;
}

Notes

We treat the list as a circle, i.,e., the last node points back to the first node
Having the external point (now called tail point at the last node also means the first node is the next node, i.e., tail.next.
The circular structure is created when a node is inserted into the empty list: node.next = node
Note the only difference between addFirst and addLast is the latter moves the tail pointer.
A header node here is not just not useful, it's actually counterproductive
- A header node would come between the last node and first node
- Having the external pointer point at the header node prevents direct access to the last node and brings us back into the traversal workd

initial state

tail == null

Efficient operations

insertion/removal at head (tail.next)
insertion at tail (tail)
insertion/removal after a specified node
- getting to that node is a different story

Requires traversal

removal at tail (tail)
insertion/removal before a specified node

Good for implementing

FIFO queue with a single pointer
round-robin scheduling strategies
- keep on moving the tail pointer to its next node

Doubly-linked Nodes in Java

class Node<E> {
	Node(E data, Node prev, Node next) {
		this.data = data;
		this.prev = prev;
		this.next = next;
	}
	Node(E data) {this(data, null, null);}
	E data;
	Node next, prev; 	// often left, right
}

Doubly-linked Linear (DL1N — Doubly-linked / Linear / 1 pointer / No header

Provides direct access to first node on list; allows two way motion

public class DL1N_Deque<E> implements Deque<E> {
	static class Node<E> {
		public Node(Node<E> prev, E data, Node<E> next) {
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
		Node(E data, Node<E> next) {this(null, data, next);}
		Node(Node<E> prev, E data) {this(prev, data, null);}
		Node(E data) {this(null, data, null);}
		Node( ) {this(null);}

		E data;
		Node<E> prev, next;
	}

	public void addFirst(E data) {
		Node<E> node = new Node<>(data, head);
		if (head != null) 
			head.prev = node;
		head = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = head;
		if (node.next != null) node.next.prev = null;
		head = node.next;
		return node.data;
	}

	public void addLast(E data) {
		if (isEmpty()) 
			addFirst(data);
		else {
			Node<E> p = head;
			while (p.next != null)
				p = p.next;
			Node<E> node = new Node<E>(p, data);
			p.next = node;
		}
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		Node<E> p = head;
		while (p != null) {
			count++;
			p = p.next;
		}
		return count;
	}

	public boolean isEmpty() {return head == null;}

	public String toString() {
		String result = "{";
		Node<E> p = head;
		while (p != null) {
			result += p.data + (p.next != null ? ", " : "");
			p = p.next;
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> head = null;
}

Notes

Note the 'clever' order of the parameters n the constructor, allowing for maximal overloading)
Note the'ugly' use of node.next.prev

initial state

head == null

Efficient operations

insertion/removal at head (rear.next)
insertion/removal after a specified node
- getting to that node is a different story
insertion/removal before a specified node
- getting to that node is a different story

Requires traversal

insertion/removal at tail (rear)

Good for implementing

Nothing new
- We have good stack and FIFO implementations, the next would be deque (list is even more general than that), and with a single head pointer we still can't implement the tail operations efficiently

Requires special-case logic for processing nodes at end of list; i.e., nodes with null left or right (or both) fields

e.g., insertBefore where the specified node is the first on the list
- have to make sure don't try to access 'next' field of prev node (whichis null)
- also need to update 'head'
similarly with removals

A List Class Using Doubly-linked Implementation

At this point, however, we do have a reasonable implementation of a List container.

class List<E> {
	static class Node<E> {
		public Node(Node<E> prev, E data, Node<E> next) {
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
		Node(E data, Node<E> next) {this(null, data, next);}
		Node(Node<E> prev, E data) {this(prev, data, null);}
		Node(E data) {this(null, data, null);}
		Node() {this(null);}

		E data;
		Node<E> prev, next;
	}
	E get(int pos) {return getNode(pos).data;}

	void set(int pos, E val) {getNode(pos).data = val;} 

	void add(int pos, E val) {
		Node<E> atPrev, atNext;
		if (pos == 0) {
			atPrev = null;
			atNext = head;
		}
		else {
			atPrev = getNode(pos-1);
			atNext = atPrev.next;
		}
		Node<E> node = new Node<E>(atPrev, val, atNext);
		if (atNext != null) atNext.prev = node;
		if (atPrev != null) atPrev.next = node;
		if (pos == 0) head = node;
		size++;
	}

	E remove(int pos) {
		Node<E> node = getNode(pos);
		E data = node.data;
		Node<E> atNext = node.next;
		Node<E> atPrev = node.prev;
		if (atPrev != null) atPrev.next = atNext;
		if (atNext != null) atNext.prev = atPrev;
		size--;
		return data;
	}

	int size() {return size;}
	
	boolean isEmpty() {return size == 0;}

	private Node<E> getNode(int pos) {
		int count = 0;
		Node<E> p = head;
		while (p != null && count < pos) {
			p = p.next();
			count++;	 
		}
		if (p == null) throw new ListException("illegal position " + pos);
		return p;
	}

	public String toString() {
		Node<E> p = head;
		String result = "";
		result += "[";
		while (p != null) {
			result += p.data + (p.next != null ? ", " : "");
			p = p.next;
		}
		result += "]";
		return result;
	}

	Node<E> head = null;
	int size = 0;
}

Notes

Being a List container, the basic operations are random-access get/set/add/insert
These, for the most part translate into traversals
- It is the two-end operations of the Deque that allowed us to avoid most of the traversals
Note the introduction of a size variable to eliminate traversal for the operation

Doubly-linked Linear With Head and Tail Pointers (DL2N — Doubly-linked / Linear / 2 pointer / No header

public class DL2N_Deque<E> implements Deque<E> {
	static class Node<E> {
		public Node(Node<E> prev, E data, Node<E> next) {
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
		Node(E data, Node<E> next) {this(null, data, next);}
		Node(Node<E> prev, E data) {this(prev, data, null);}
		Node(E data) {this(null, data, null);}
		Node() {this(null);}

		E data;
		Node<E> prev, next;
	}

	public void addFirst(E data) {
		Node<E> node = new Node<>(data, head);
		if (isEmpty()) 
			tail = node;
		else	
			head.prev = node;
		head = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = head;
		if (node.next != null) 
			node.next.prev = null;
		head = node.next;;
		return node.data;
	}

	public void addLast(E data) {
		if (isEmpty()) 
			addFirst(data);
		else {
			Node<E> node = new Node<>(tail, data);
			tail.next = node;
			tail = node;
		}
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		Node<E> p = head;
		while (p != null) {
			count++;
			p = p.next;
		}
		return count;
	}

	public boolean isEmpty() {return head == null;}

	public String toString() {
		String result = "{";
		Node<E> p = head;
		while (p != null) {
			result += p.data + (p.next != null ? ", " : "");
			p = p.next;
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> head = null, tail = null;
}

Notes

The combination of the two pointers and the double-links remove the traversal from removeLast and as a result provide us with an O(1) linked deque implementation.

Doubly-linked Circular (DC1N — Doubly-linked / Circular / 1 pointer / No header

Provides direct access to 'last' and 'first' node on list; eliminates null next/prev fields at end

public class DC1N_Deque<E> implements Deque<E> {
	static class Node<E> {
		public Node(Node<E> prev, E data, Node<E> next) {
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
		Node(E data) {this(null, data, null);}
		Node() {this(null);}

		E data;
		Node<E> prev, next;
	}

	public void addFirst(E data) {
		Node<E> node = new Node<>(data);
		if (head == null) {
			node.next = node.prev = node;
		}
		else {
			node.prev = head.prev;
			head.prev.next = node;
			node.next = head;
			head.prev = node;
		}
		head = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = head;
		if (head.next == head) 
			head = null;
		else {
			node.next.prev = node.prev;
			node.prev.next = node.next;;
			head = node.next;
		}
		return node.data;
	}

	public void addLast(E data) {
		if (head == null) 
			addFirst(data);
		else {
			Node<E> node = new Node<>(head.prev, data, head);
			node.prev = head.prev;
			head.prev.next = node;
			node.next = head;
			head.prev = node;
		}
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		if (head != null) {
			Node<E> p = head;
			do {
				count++;
				p = p.next;
			} while (p != head);
		}
		return count;
	}

	public boolean isEmpty() {return head == null;}

	public String toString() {
		String result = "{";
		if (head != null) {
			Node<E> p = head;
			do {
				result += p.data + (p.next != head ? ", " : "");
				p = p.next;
			} while (p != head);
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> head = null;
}

Notes

initial state

head == null

Efficient operations

insertion/removal at head (rear.next)
insertion/removal at tail (rear)
insertion/removal after a specified node
- getting to that node is a different story
insertion/removal before a specified node
- getting to that node is a different story

Good for implementing

Deque
- and not bad idea to leverage stack and FIFO queue
Reduces average traversal to get to a particular index from n/2 to n/4 (start from front OR rear).

Requires special-case logic for updating 'head' during empty → non-empty and non-empty → empty operations

Doubly-linked Linear Circular With Header Node (DC1H — Doubly-linked / Circular / 1 pointer / Header

Sounds the most complicated, but in fact, eliminates all special logic.

Provides direct access to 'last' and 'first' node on list; eliminates null next/prev fields at end
Upon list creation, a 'dummy' node — containing no data &msash; is created and head is pointed to that node.
```
head == new Node(); 
```
To the right of the node is the beginning of the list, to the left the tail.
There is no more special logic of any sort

public class DC1H_Deque<E> implements Deque<E> {
	static class Node<E> {
		public Node(Node<E> prev, E data, Node<E> next) {
			this.prev = prev;
			this.data = data;
			this.next = next;
		}
		Node(E data) {this(null, data, null);}
		Node() {this(null);}

		E data;
		Node<E> prev, next;
	}

	DC1H_Deque() {
		 header = new Node<>();
		 header.next = header.prev = header;
	}

	public void addFirst(E data) {
		Node<E> node = new Node<>(header, data, header.next);
		header.next.prev = node;
		header.next = node;
	}

	public E removeFirst() {
		if (isEmpty()) throw new CollectionException("Deque", "removeFirst", "empty container"); 
		var node = header.next;
		node.next.prev = header;
		header.next = node.next;;
		return node.data;
	}

	public void addLast(E data) {
		Node<E> node = new Node<>(header.prev, data, header);
		header.prev.next = node;
		header.prev = node;
	}

	public E removeLast();			// you are to implement this method
		
	public int size() {
		int count = 0;
		Node<E> p = header.next;
		while (p != header) {
			count++;
			p = p.next;
		}
		return count;
	}

	public boolean isEmpty() {return header.next == header && header == header.prev;}

	public String toString() {
		String result = "{";
		Node<E> p = header.next;
		while (p != header) {
			result += p.data + (p.next != header ? ", " : "");
			p = p.next;
		}
		result += "}";
		return result;
	}

	public int capacity() {return -1;}
		
	private Node<E> header;
}

Notes

initial state

head == headerNode;

Efficient operations

insertion/removal at head (rear.next)
insertion/removal at tail (rear)
insertion/removal after a specified node
- getting to that node is a different story
insertion/removal before a specified node
- getting to that node is a different story

Good for implementing

Deque
- and not bad idea to leverage stack and FIFO queue
Reduces average traversal to get to a particular index from n/2 to n/4 (start from front OR rear).

Basic Insertion/Removal Operations for Lists of Nodes

As we've seen above, different linked list implementations support different sets of efficient insertion/removal methods: insertFront, removeFront, insertLast, removeLast, insertAfter, removeAfter.

If we are willing to traverse the list, we can also consider:

remove: remove the first element equal to some specified value (why not insert?)

Note that this version of remove really belongs to the associative world, as it it value-based. We are presenting it here to introduce a standard technique in linked list processing.

`remove`

remove: remove the first element equal to some specified value (content-based remove)

We will implement this using a singly linked linear list

boolean remove(E data) {
	Node p = head, q = null; 

	while (p != null && data != p.data) {
		q = p;		// this is the piggyback action
		p = p.next;
	}
	if (p == null) 
		return false;
	else if (q == null)
		removeFront();
	else
		removeAfter(q);
}

remove, uses a technique known as piggybacking
- One pointer 'scouts' ahead (eventually going too far), the other stays back and can be used for the actual removal operation
Have to take into account both removing from front as well as from middle
the removeFront method is nothing more than the pop method of the singly linked linear stack implementation of above

Traversive Operations on Lists of Nodes

These operations work on the list as a whole

length: returns number of elements in a list
toString / returns a String representation of the list elements
clear: removes all the elements from a list
find: returns whether a particular value is an element of a list
copy: copy the elements of a list to a new list
remove

Iterative Versions of the Traversive Operations

Typical structure of an iterative function operating on a list of nodes:

... someFunc(Node head...) {
	while (head != null) {						// head passed by value, can modify it without worry
		...head.data		// process data of node pointed to by head
		head = head.next;			// go to next node
	}
	return;
}

length

int length(Node head) {
	int count = 0;
	while (head != null) {
		count++;
		head = head.next;
	}
	return count;
}

copy

Node copy(Node head) {
	Node lastNode = null, newHead = null;
	while (head != null) {
		Node q = new Node(head.data);
		if (newHead = null) 						// only true one (first time)
			newHead = q;
		else
			lastNode.next = q;
		lastNode = q;
		head = head.next;
	}
	return newHead;
}

Recursion and Lists of Nodes

Lists of nodes can be processed using recursion
- This is because lists of nodes have a recursive structure/definition:
  - A list of nodes is either:
    - empty (i.e., contains no nodes / head contains nullptr, or
    - a node with a next field pointing to a list of nodes

Recursive Versions of the Traversive Operations

Typical structure of a recursive function operating on a list of nodes:

... someFunc(Node head...) {
	if (head == null)				// list is empty
		return;
	else {
		... head.data ... 		// process first element of the list
		someFunc(head.next);	// call the function recursively on the rest of the list
	}
}

length

int length(Node head) {
	if (head == null) 
		return 0;
	else
		return length(head.next) + 1;
}

int length(Node head) {return head != null ? length(head.next) + 1 : 0;}

copy

Node copy(Node head) {
	if (head == null) return null;
	return new Node(head.data, copy(head.next));
}

Recursion in the Presence of Classes

Lists of nodes are recursive, linked lists aren't
- A list of nodes is either an empty list, or a node followed by a list of nodes
- A linked list is an object with a head pointer; there is no recursive structure
- If linked lists are not recursive, how do we code the recursive versions of the trasversives on a linked list object?
  - The solutionis to use delegation
    - Have a public function that adds the recursive parameter and calls a private recursive counterpart:
```
class LinkedList {
	…
	public int length() {return length(head);}	// can't be recursive, but can call a private recursive helper function
	…
	private int length(Node p) {			recurses on its Node parm
		if (p == null) return 0;
		return 1 + length(p.next);
	}
	Node head;
	…	
};
			
```

CIS 3130 Data Structures Lecture 08 Linked Implementations

Motivation

Implicit vs Explicit Addressing

Nodes: The Atoms of Linked Implementations

Nodes in Java

Operations Involving a Specified Node

insertAfter

removeAfter

Lists of Nodes — Linked Lists

Advantages of Linked Lists

Disadvantages of Linked Lists

Linked Lists in Java

Some Tips on Working with Linked Lists

A Progression of Linked Lists

Singly-linked Linear (SL1N — Singly-linked / Linear / 1 pointer / No header

initial state

Efficient operations

Requires traversal

'Random access' of nodes

Good for implementing

Stack implementation Using a Singly Linked Linear List

push

pop

Other Comments

Header (Dummy) Nodes

For 'Meta' Data (Historical)

To Eliminate Special Logic (Current)

Singly-linked Linear With Header Node (SL1H — Singly-linked / Linear / 1 pointer / Header

initial state

Efficient operations

Requires traversal

Good for implementing

Singly-linked Linear With Head and Tail Pointers (SL2N — Singly-linked / Linear / 2 pointers / No header

initial state

Efficient operations

Requires traversal

Good for implementing

FIFO Queue Implementation Using Singly Linked Linear List with Head and Tail Pointers

add (to rear)

remove (from front)

Singly-linked Circular with Single Pointer to 'Last' Node on List (SC1N — Singly-linked / Circular / 1 pointer / No header

initial state

Efficient operations

Requires traversal

Good for implementing

Doubly-linked Nodes in Java

Doubly-linked Linear (DL1N — Doubly-linked / Linear / 1 pointer / No header

initial state

Efficient operations

Requires traversal

Good for implementing

A List Class Using Doubly-linked Implementation

Doubly-linked Linear With Head and Tail Pointers (DL2N — Doubly-linked / Linear / 2 pointer / No header

Doubly-linked Circular (DC1N — Doubly-linked / Circular / 1 pointer / No header

initial state

Efficient operations

Good for implementing

Doubly-linked Linear Circular With Header Node (DC1H — Doubly-linked / Circular / 1 pointer / Header

initial state

Efficient operations

Good for implementing

Basic Insertion/Removal Operations for Lists of Nodes

remove

Traversive Operations on Lists of Nodes

Iterative Versions of the Traversive Operations

Recursion and Lists of Nodes

Recursive Versions of the Traversive Operations

Recursion in the Presence of Classes

CIS 3130
Data Structures
Lecture 08
Linked Implementations

`insertAfter`

`removeAfter`

`push`

`pop`

`add (to rear)`

`remove (from front)`

`remove`