Linked lists: Permutations & implementations

Synopsis: We discuss linked list abstract data types, reasons for implementation and implementation specifications/examples in JavaScript.

II. Specifications and implementations

A linked list is a data structure comprised of linked nodes, each referencing the next link in the logical chain. You can imagine a linked list as a train where each node is a train car. A train can only have two possible links: the link ahead of it and the link behind.

If you want to access a specific train car while on the train, you will need to traverse the train cars sequentially until you reach your desired car - for the most part anyway.

There can be variations in the manner in which we traverse and permutations of order. Among the abstract data types (ADT) associated with linked lists we can have singly-linked lists (uni-directional traversal), doubly-linked lists (bi-directional traversal), circular linked lists (bi-directional with the train connected at each end) with many permutations affecting search, traversal and modification.

Singly-linked list

Begins the data structure with a head.
Ends the data structure with a null reference.
Limits traversal to uni-directional behavior.

In example 1.1 below, the beginning of the singly-linked list (or the head) contains the data element 12, and a link or pointer^[1] to the next link in the chain, and so the chain continues until the chain reaches a null value. In this ADT, traversal behavior is limited to being uni-directional. You begin traversal from the head.

1.1 Singly-linked list example, Wikipedia

Doubly-linked list

Begins data structure with a head node.
Indicates last node with a tail node.
Ends data structure with null reference.
Permits bi-directional traversal behavior.

The doubly-linked list in our next example (1.2) begins again with 12, but the key difference in the ADT is that once you traverse to the next node (containing 99), you can traverse back the way you came! A doubly-linked list references with a pointer both the next and the previous node. The doubly-linked list begins with a head and ends with a tail.

1.2 Doubly-linked list example, Wikipedia

Circular linked list

Links the beginning node and end node of the data structure together to create a circular reference.

The circular linked list in our next example (1.3) does away with having a concrete head and tail (we don't have a null value), and instead glues the two together.

1.3 Circular linked list example, Wikipedia

The reason we might construct a linked list could have to do with memory. In many other languages, when an array is created, it has a specific amount of memory allocated to that array in a specific and contiguous memory address range; so all the array elements are kept together. If you need, for example, to significantly change your array contents to be greater, the array would have to be reallocated elsewhere in memory.

While a linked list will not ensure that memory is contiguously allocated to nodes inside a list; it will prevent ensure that expensive operations such as the reallocation are rendered unnecessary.

In JavaScript, arrays are dynamic in length and actually just indices for values. Assuming that you have not frozen your array, you are able to add and remove elements from it at will. This means that arrays in JavaScript are not guaranteed to be densely populated in memory (contiguous), so JavaScript arrays do not behave as you would expect an array to operate.^[1:1]

Specifications & implementations

Before we begin writing code for our linked list implementations, we should first develop specifications for the linked list ADTs we've outlined above (with some variations to come).

We will create our specifications using JSDoc syntax. You can read more about why we do this in our article Starting JavaScript Right: Writing the specification.

Singly-linked list specification & implementation

Our implementation for a singly-linked list will require two constructor classes: the Node and LinkedList. Since we know that we will later be working on a doubly-linked list, we'll go ahead and name our Node class the SingleNode and our linked list as simply LinkedList.

At a high level: we will restrict all interface methods to the list to the LinkedList class. Most important among our interface methods, we will need the ability to add and remove nodes from our linked list, and each of these will need an argument.

Everything else will be a helper method in management of our linked list.


// We will need to pass in data with addNode so that
// our linked list actually has substance.

addNode(data)

// removeNode doesn't necessarily require an argument.
// The default operation can just be to pop() off the 
// most recent node. But we will include one so that we
// can granularly manage our linked list.

removeNode(position)


/**
* SingleNode
* @constructor
* @param {*} data - Any form of data.
* @desc Builds node for use in singly-linked list.
*/

class SingleNode {
	constructor(data) {
		this.data = data;
		this.next = null;
	}

}



/**
* SingleNode
* @constructor
* @param {*} data - Any form of data.
* @desc Builds node for use in singly-linked list.
*/

class SingleNode {
	constructor(data) {
		this.data = data;
		this.next = null;
	}	
}

/**
* LinkedList
* @constructor
* @desc Builds empty singly-linked list.
*/


class LinkedList {
	constructor() {
		this._storage = [];
		this.head = null;
	}

	/**
	* addNode
	* @method
	* @param {*} data - Any form of data.
	* @desc Adds node and returns added node.
	* @returns {Array} Containing newly added node.
	*/

	addNode(data) {
		if (!data) {
			throw new Error('Data required for node');
		}

		let node = new SingleNode (data),
		currentNode = this.head;

		if (!currentNode) {
			this._storage.push(node);
			this.head = node;

			return node;
		}

		while (currentNode.next) {
			currentNode = currentNode.next;
		}
		
		currentNode.next = node;
		this._storage.push(node);
		return node;
	}

	/**
	* removeNode(position)
	* @method
	* @param {number} position - Expects an integer.
	* @desc Removes node from linked list based on position
	*	passed in as argument. If no position, defaults
	*	to removing last node in list. 	
	* @returns Returns deleted node object.
	*/
	
	removeNode(position) {

		// Removal can be a little tough. We must account
		//	for the pointer to the next code on any
		//	node we pass in for removal. Thus, we
		//	instantiate the nodeBefore/nodeToBe variables
		//	to assist us with maintaining pointer integrity.
		let count = 1,
		currentNode = this.head,
		nodeBeforeDeleted = null,
		nodeToBeDeleted = null,
		deletedNode = null,

		// We construct an err object so we can pass in
		// 	a customized error message for each of our
		//	error condition; making it easier to maintain.
		err = {
			empty: 'List is empty',
			nonExistent: 'Position non-existent',
			isNaN: 'Position argument is not a number'
		};

		if (this._storage.length === 0) {
			throw new Error (err.empty);
		} else if (position > this._storage.length) {
			throw new Error(err.nonExistent);
		} else if (typeof position != 'number') {
			throw new Error (err.isNaN);
		}

		if (position === count) {
			this.head = currentNode.next;
			nodeToBeDeleted = currentNode;
			deletedNode = nodeToBeDeleted;
			nodeToBeDeleted = null;

			return deletedNode;
		}

		while (count < position) {
			nodeBeforeDeleted = currentNode;
			deletedNode = currentNode.next;
			count++;
		}

		nodeBeforeDeleted.next = deletedNode.next;
		deletedNode = currentNode;
		currentNode = null;
		
		return deletedNode;
	}

	/**
	* size
	* @method
	* @returns {Number} Returns the current size of the linked list,
	*	based on node depth.
	*/

	size() {
		return this._storage.length;
	}

	/**
	* clear
	* @method
	* @desc Removes all nodes in the linked list.
	* @returns {Array} Returns empty array.

	*/
	
	clear() {
		return this.storage = [];
	}

	/**
	* print(position)
	* @method
	* @param {number} position - Expects an integer.
	* @desc Prints a node to the console based on the
	*	position argument passed in. If no position
	*	is specified, defaults to printing the list.
	* @returns Returns node object at specified position or 
	*	list.
	*/

	print(position) {
		let currentNode = this.head,
		count = 1,
		err = {
			empty: 'List is empty',
			nonExistent: 'Position non-existent',
			isNaN: 'Position argument is not a number'
		};
		
		if (!position) {
			return this._storage;
		}
		
		if (this._storage.length === 0) {
			throw new Error (err.empty);
		} else if (position > this._storage.length) {
			throw new Error (err.nonExistent);
		} else if (typeof position != 'number') {
			throw new Error (err.isNaN);
		}

		while (count < position) {
			currentNode = currentNode.next;
			count++;
		}
		
		return currentNode;
	}
}