Implementing the Singly Linked List
Posted by in Programming on
If you set out to build a dog house, you probably wouldn't hire a structural engineer to design it. After all, it doesn't take much more than some plywood, wooden beams, nails, glue, and paint to slap together a dog house. But you might take the time to at least sketch it out on a napkin, since wasting time can be frustrating and wasting materials can be expensive.
If you set out to build a house, however, you (hopefully) wouldn't just send a dozen people out to start wildly slapping bricks down wherever they please. Even if each person perfectly builds the room they envisioned, there is no guarantee that their collective work would result in a house. The larger the project and the more people you add to that project, the more important it becomes to plan and coordinate activity.
In Engineering the Singly Linked List, we walked through the planning/engineering for a typical Singly Linked List. The resulting diagrams should provide us with enough information to create a data structure that behaves according to the rules we defined; while still affording us enough freedom that we aren't bound to any particular language. This entry will implement our Singly Linked List in PHP, C++, and JavaScript with a heavy focus on the coding aspect. By the end, you should understand how to create a prototype of this data structure in your favorite object-oriented programming language.
Singly Linked List Interface
An Interface is a programming pattern that is used to define the contract that will be used when interacting with objects instantiated from a class, as well as the results that those interactions should yield. Different programming languages have different conventions for implementing this pattern, but my preferred technique is to only include the public methods that external code would use to access the class and to use getters/setters in place of public attributes. This ensures that an interface fulfills its purpose of setting a contract between a class of objects and the external code, while still affording flexibility to any developer in implementing that interface.
PHP Interface
In PHP, an interface can be implemented by using the appropriately named interface keyword in place of the class keyword when writing a class definition.
interface ListInterface
{
public function insert($value, $index = null);
public function get($index);
public function set($index, $value);
public function remove($index, $count = 1);
public function count();
}
```
## C++ Interface ## {#cpp-list-interface}
In C++, an interface may be implemented using an abstract class. We can do this by writing a class where the ```public``` methods that our list needs to fulfill are marked as ```virtual```. The first challenge steps from C++ being a strictly typed language: our list must be aware of what kind of data it is holding. The naïve way to handle this is to write separate classes for each data type. A better way to do it is to make our compiler do that for us by using templates.
Unfortunately, templates and virtual functions can't be used on the same class. In order to find a workaround, we must define what constitutes an interface.
1. The class must not be instantiable.
2. The class must be inheritable.
3. The class must declare methods.
4. The class must not define methods.
5. Derivative classes must not be instantiable unless all methods are defined.
Based on this criteria, we can emulate a templated interface by declaring methods without implementing methods. Templates cannot have their methods defined in ```*.cpp``` files, so this will prevent the class from being instantiated. On compile-time, the compiler will detect that those methods were not defined and throw an error if an undefined method is invoked. We retain the ability to use templates, and the compiler will still throw errors if we do not define the methods in our child-classes.
``` cpp
template
class ListInterface
{
public:
ListInterface& insert(T value);
ListInterface& insert(T value, unsigned int index);
T get(unsigned int index);
ListInterface& set(unsigned int index, T value);
ListInterface& remove(unsigned int index, unsigned int count = 1);
unsigned int count();
};
```
## JavaScript (ES5) Interface ## {#js-list-interface}
JavaScript has some eccentricities that make it unique from both PHP and C++ in that it doesn't have a programmatically enforced concept of class inheritance. As a result, there is no "right" way to write an interface. One technique for emulating this behavior is to check for the existence of properties before invoking them and accept any object that fits the description — a process known as Duck Typing.
We can containerize our Duck Typing by defining a class to whose purpose is to check if objects implement a set of methods. The Interface class is outside of the scope of this entry, but I encourage you to look it over on my [GitHub][github-interface].
``` javascript
var ListInterface = new Interface('ListInterface', [
'insert',
'get',
'set',
'remove',
'count',
]);
```
# Writing the List Node Interface # {#node-interface}
As discussed in [Engineering the Singly Linked List], a linked list must use nodes to carry a value and some positional data so the list can be traversed. The nodes should only be referenced from within the data structure, but we should define an interface anyway to avoid inadvertently binding code to a single implementation.
## PHP Singly-Linked Node Interface ## {#php-node-interface}
In PHP, an interface may inherit from other interfaces using the ```extends``` keyword.
``` php
interface NodeInterface
{
public function getValue();
public function setValue($value);
}
interface SinglyLinkedNodeInterface extends NodeInterface
{
public function getNextNode();
public function setNextNode($node);
}
```
## C++ Singly-Linked Node Interface ## {#cpp-node-interface}
In C++, interfaces (abstract classes) are just like any other class, and they inherit just like any other class.
``` cpp
template
class NodeInterface
{
NodeInterface& setValue(T value);
T getValue();
};
template
class SinglyLinkedNodeInterface : public NodeInterface
{
public:
NodeInterface* getNextNode();
NodeInterface& setNextNode(NodeInterface* node);
};
```
## JavaScript Singly-Linked Node Interface ## {#js-node-interface}
In JavaScript, class inheritance works differently. The ```Interface``` class is designed to do this by taking an array of ```Interface``` classes in an array as the third parameter of the constructor.
``` javascript
var NodeInterface = new Interface('NodeInterface', [
'setValue',
'getValue',
]);
var SinglyLinkedNodeInterface = new Interface('NodeInterface', [
'setNextNode',
'getNextNode',
], [NodeInterface]);
```
# Implementing the Singly Linked Node Interface # {#implement-node}
This is the final step before the data structure can be used. In order to implement the interface, the classes must be fully declared and defined. According to our models, the Singly Linked Node should have getters and setters for the "next" node in a chain, and for the value within the node. We can represent a node being the "last" node in one direction by marking it as ```null```.
## PHP Singly Linked Node ## {#php-implement-node}
Implementing an interface in PHP is done with the ```implements``` keyword. If the class does not adhere to the declarations in the interface, then PHP will throw an exception at runtime.
``` php
class SinglyLinkedNode implements SinglyLinkedNodeInterface
{
/**
* SinglyLinkedNode Constructor
* @param mixed $value Value to hold within the node
*/
public function __construct($value)
{
parent::__construct($value);
$this->nextNode = null;
}
/**
* Gets the next node in the chain
* @return SinglyLinkedNodeInterface
*/
public function getNextNode()
{
return $this->nextNode;
}
/**
* Sets the next node in the chain
* @param SinglyLinkedNode $node
*/
public function setNextNode($node)
{
$this->nextNode = $node;
}
/**
* Retrieves the value contained within the node
* @return mixed
*/
public function getValue()
{
return $this->value;
}
/**
* Sets the value contained within the node
* @param mixed $value value to carry
* @return $this
*/
public function setValue($value)
{
return $this->value = $value;
}
/**
* Value being carried by this node
* @var mixed
*/
protected $value;
/**
* The next node in the chain, or null if this is the last node
* @var SinglyLinkedNodeInterface
*/
protected $nextNode;
}
C++ Singly Linked Node
Implementing an interface in C++ is done by extending a class from the interface. As with the interfaces, the Node class must identify the data type that the node will carry. C++ has a more robust implementation of memory management than PHP does, and so we must consider the difference betweeen pointers and references. Any node reference that can be NULL must be a pointer (*); but any other reference should use the reference pointer (&) to avoid null-pointer segmentation fault.
template<typename T>
class SinglyLinkedNode :
public SinglyLinkedNodeInterface<T>
{
public:
/**
* SinglyLinkedNode Constructor
* @param T value Value to hold within the node
*/
SinglyLinkedNode(T value) :
Node<T>(value),
nextNode(NULL)
{
// empty constructor
}
/**
* Gets the next node in the chain
* @return SinglyLinkedNode&
*/
SinglyLinkedNode<T>* getNextNode()
{
return this->nextNode;
}
/**
* Sets the next node in the chain
* @param SinglyLinkedNode* node
*/
SinglyLinkedNode<T>& setNextNode(SinglyLinkedNode<T>* node)
{
this->nextNode = node;
return *this;
}
/**
* Retrieves the value contained within the node
* @return T
*/
T getValue()
{
return this->value;
}
/**
* Sets the value contained within the node
* @param T value value to carry
* @return *this
*/
SinglyLinkedNode<T>& setValue(T value)
{
this->value = value;
return *this;
}
protected:
SinglyLinkedNode<T>* nextNode;
};JavaScript Singly Linked Node
Since interfaces do not technically exist in JavaScript, there is no need to explicitly inherit from an interface. However, the Interface class we completed earlier is designed to do the Duck Typing for us whenever the node needs to be validated.
/**
* Variant of a Node that links in one direction
*
* @param {*} value Value the node should carry
* @constructor
* @implements {NodeInterface}
*/
function SinglyLinkedNode(value)
{
this.value = value;
this.nextNode = null;
}
SinglyLinkedNode.prototype = {
/**
* Retrieves the value contained within the node
* @return {*}
*/
getValue: function() {
'use strict';
return this.value;
},
/**
* Sets the value contained within the node
* @param {*} value
* @chainable
*/
setValue: function(value) {
'use strict';
this.value = value;
return this;
},
/**
* Gets the next node in the chain
* @return {SinglyLinkedNodeInterface}
*/
getNextNode: function() {
return this.nextNode;
},
/**
* Sets the next node in the chain
* @param {SinglyLinkedNodeInterface} node
* @chainable
*/
setNextNode: function(node) {
if (null !== node) {
SinglyLinkedNodeInterface.implementedBy(node);
}
this.nextNode = node;
return this;
}
};Implementing the Linked List Interface
The final step before we have a functional linked list is to implement our interface. Since this is where all of the business logic exists, this is the most complicated class to write. Fortunately, we've already decided how this structure is supposed to behave, and we have our process flow diagrams to code against.
PHP Singly Linked List
Just like with the Node class, our list will be implemented from an interface.
class SinglyLinkedList implements ListInterface
{
/**
* Creates a singly-linked list data structure
*/
public function __construct()
{
$this->headNode = null;
}
/**
* Inserts a new value at the requested index. If no index is provided, then
* assumes that the value should be inserted at the end of the data
* structure.
*
* @param mixed value
* @param integer index
*
* @return SinglyLinkedList
*/
public function insert($value, $index = null)
{
$node = new SinglyLinkedNode($value);
if (is_null($index) && is_null($this->headNode)) {
$this->headNode = $node;
return $this;
}
if (null === $index) {
$this->getLastNode()->setNextNode($node);
return $this;
}
if (0 == $index) {
$node->setNextNode($this->headNode);
$this->headNode = $node;
return $this;
}
$previousNode = $this->getNode($index - 1);
$node->setNextNode($previousNode->getNextNode());
$previousNode->setNextNode($node);
return $this;
}
/**
* Retrieves a value from the identified index
*
* @param integer $index
* @return mixed value stored at the index
*/
public function get($index)
{
return $this->getNode($index)->getValue();
}
/**
* Updates a value at the identified index
*
* @param integer $index
* @param mixed $value
* @return $this
*/
public function set($index, $value)
{
$this->getNode($index)->setValue($value);
return $this;
}
/**
* Removes "count" nodes, starting from the identified index
*
* @param integer index
* @param integer count (default: 1)
* @return $this
*/
public function remove($index, $count = 1)
{
$nextNode = $this->getNode($index + $count - 1)->getNextNode();
if (0 === +$index) {
$this->headNode = $nextNode;
return $this;
}
$this->getNode($index - 1)->setNextNode($nextNode);
return $this;
}
/**
* Counts the number of nodes in the linked list
*
* @return integer
*/
public function count()
{
$count = 0;
$node = $this->headNode;
while (!is_null($node)) {
$node = $node->getNextNode();
++$count;
}
return $count;
}
/**
* Retrieves the node at the identified index
*
* @param integer index
* @return SinglyLinkedNodeInterface
*/
protected function getNode($index)
{
if (!is_null($index) && (!is_int($index) || 0 > intval($index))) {
throw new OutOfBoundsException("Expected $index to be a positive integer");
}
$node = $this->headNode;
for ($i = 0; $i < $index; ++$i) {
$node = $node->getNextNode();
if (!$node) {
throw new OutOfBoundsException("Expected $index to be within length of list");
}
}
return $node;
}
/**
* Retrieves the last node in the structure
*
* @return SinglyLinkedNodeInterface
*/
protected function getLastNode()
{
$node = $this->headNode;
while ($node && $node->getNode()) {
$node = $node->getNode();
}
return $node;
}
protected $headNode;
}
C++ Singly Linked List
The Singly Linked List, as implemented in C++, will follow a very similar pattern:
#include <stdexcept>
template<typename T>
class SinglyLinkedList : ListInterface<T>
{
public:
/**
* Creates a singly-linked list data structure
*/
SinglyLinkedList() : headNode(NULL)
{
// empty constructor
}
/**
* Inserts a new value at the requested index. If no index is provided, then
* assumes that the value should be inserted at the end of the data
* structure.
*
* @param T value
*
* @return *this
*/
SinglyLinkedList<T>& insert(T value)
{
if (NULL == this->headNode) {
return this->insert(value, 0);
}
SinglyLinkedNode<T>& lastNode = this->getLastNode();
SinglyLinkedNode<T>* node = new SinglyLinkedNode<T>(value);
lastNode.setNextNode(node);
return *this;
}
/**
* Inserts a new value at the requested index. If no index is provided, then
* assumes that the value should be inserted at the end of the data
* structure.
*
* @param T value
* @param uint= index
*
* @return *this
*/
SinglyLinkedList<T>& insert(T value, unsigned int index)
{
SinglyLinkedNode<T>* node = new SinglyLinkedNode<T>(value);
if (0 == index) {
node->setNextNode(this->headNode);
this->headNode = node;
return *this;
}
SinglyLinkedNode<T>& previousNode = this->getNode(index - 1);
node->setNextNode(previousNode.getNextNode());
previousNode.setNextNode(node);
return *this;
}
/**
* Retrieves a value from the identified index
*
* @param uint index
* @return T value stored at the index
*/
T get(unsigned int index)
{
return this->getNode(index).getValue();
}
/**
* Updates a value at the identified index
*
* @param uint index
* @param T value
*
* @return *this
*/
SinglyLinkedList<T>& set(unsigned int index, T value)
{
this->getNode(index).setValue(value);
return *this;
}
/**
* Removes "count" nodes, starting from the identified index
*
* @param uint index
* @param uint=1 count
*
* @return *this
*/
SinglyLinkedList<T>& remove(unsigned int index, unsigned int count = 1)
{
SinglyLinkedNode<T>* nextNode = this->getNode(index + count - 1).getNextNode();
if (0 == index) {
this->headNode = nextNode;
return *this;
}
this->getNode(index - 1).setNextNode(nextNode);
return *this;
}
/**
* Counts the number of nodes in the linked list
*
* @return uint
*/
unsigned int count()
{
unsigned int count = 0;
SinglyLinkedNode<T>* node = this->headNode;
while (node) {
node = node->getNextNode();
++count;
}
return count;
}
protected:
/**
* Retrieves the node at the identified index
*
* @param uint index
* @return SinglyLinkedNodeInterface&
*/
SinglyLinkedNode<T>& getNode(unsigned int index)
{
SinglyLinkedNode<T>* node = this->headNode;
for (unsigned int i = 0; i < index; ++i) {
node = node->getNextNode();
if (!node) {
throw new std::out_of_range("Expected index to be within length of list");
}
}
return *node;
}
/**
* Retrieves the last node in the structure
*
* @return SinglyLinkedNodeInterface&
*/
SinglyLinkedNode<T>& getLastNode()
{
SinglyLinkedNode<T>* node = this->headNode;
while (node && node->getNextNode()) {
node = node->getNextNode();
}
if (!node) {
throw new std::out_of_range("Expected index to be within length of list");
}
return *node;
}
SinglyLinkedNode<T>* headNode;
};JavaScript Singly Linked List
Finally, implementing the list in JavaScript will follow the same pattern as the Node and the other linked list models:
/**
* Creates a singly-linked list data structure
*
* @constructor
* @implements {ListInterface}
*/
function SinglyLinkedList()
{
'use strict';
this.headNode = null;
}
SinglyLinkedList.prototype = {
/**
* Inserts a new value at the requested index. If no index is provided, then
* assumes that the value should be inserted at the end of the data
* structure.
*
* @param {*} value
* @param {integer=} index
*
* @chainable
*/
insert: function(value, index) {
'use strict';
// validate paramters
if (0 === arguments.length) {
throw new Error('SinglyLinkedList.insert requires at least one argument');
}
if (1 === arguments.length) {
index = null;
}
if (null !== index && +index !== (+index|0)) { // convert to integer
throw new Error('SinglyLinkedList.insert expects index to be integer, null, or undefined');
}
// business logic
var node = new SinglyLinkedNode(value);
if (null === index && null === this.headNode) {
this.headNode = node;
return this;
}
if (null === index) {
this.getLastNode().setNextNode(node);
return this;
}
if (0 === +index) {
node.setNextNode(this.headNode);
this.headNode = node;
return this;
}
var previousNode = this.getNode(index - 1);
node.setNextNode(previousNode.getNextNode());
previousNode.setNextNode(node);
return this;
},
/**
* Retrieves a value from the identified index
*
* @param {integer} index
* @return {*} value stored at the index
*/
get: function(index) {
'use strict';
// check parameters
if (0 === arguments.length) {
throw new Error('SinglyLinkedList.get requires one argument');
}
// business logic
return this.getNode(index).getValue();
},
/**
* Updates a value at the identified index
*
* @param {integer} index
* @param {*} value
*
* @chainable
*/
set: function(index, value) {
'use strict';
// check parameters
if (2 !== arguments.length) {
throw new Error('SinglyLinkedList.set expects two arguments');
}
// business logic
this.getNode(index).setValue(value);
return this;
},
/**
* Removes "count" nodes, starting from the identified index
*
* @param {integer} index
* @param {integer=} count (default: 1)
*
* @chainable
*/
remove: function(index, count) {
'use strict';
// check parameters
if (0 === arguments.length) {
throw new Error('SinglyLinkedList.remove requires 1 or 2 arguments');
}
if (1 === arguments.length) {
count = 1;
}
if (1 > count) {
throw new Error('SinglyLinkedList.remove requires count parameter to be greater than 0');
}
if (+count !== (+count)|0) {
throw new Error('SinglyLinkedList.remove expected count paramter to be an integer');
}
// business logic
var nextNode = this.getNode(index + count - 1).getNextNode();
if (0 === +index) {
this.headNode = nextNode;
return this;
}
this.getNode(index - 1).setNextNode(nextNode);
return this;
},
/**
* Counts the number of nodes in the linked list
*
* @return {integer}
*/
count: function() {
'use strict';
var node = this.headNode;
var count = 0;
while (node) {
node = node.getNextNode();
++count;
}
return count;
},
/**
* Retrieves the node at the identified index
*
* @param {integer} index
* @return {SinglyLinkedNodeInterface}
*
* @protected
*/
getNode: function(index) {
'use strict';
var node = this.headNode;
for (var i = 0; i < index; ++i) {
node = node.getNextNode();
if (!node) {
throw new Error("Expected index to be within length of the list");
}
}
return node;
},
/**
* Retrieves the last node in the structure
*
* @return {SinglyLinkedNodeInterface}
*
* @protected
*/
getLastNode: function() {
'use strict';
var node = this.headNode;
while (node && node.getNextNode()) {
node = node.getNextNode();
}
return node;
},
};Hello, World
Now that the linked list is in place, it's time to check to make sure it's working properly. Let's test each of these functions with a simple "Hello World" example. Each of these examples should yield the same result:
hello world! hello! count: 1 goodbye!!PHP Example
In this example, the server should echo the Hello World example to the page.
$list = new SinglyLinkedList();
$list->insert('world')->insert('hello', 0);
echo $list->get(0), ' ', $list->get(1), '!', "\r\n";
echo $list->remove(1)->get(0), '!', "\r\n";
echo 'count: ', $list->count(), "\r\n";
echo $list->set(0, 'goodbye!')->get(0), '!', "\r\n";C++ Example
In this example, the server should print the Hello World example to the console where the program was run.
SinglyLinkedList<std::string> list;
list.insert("world").insert("hello", 0);
std::cout << list.get(0) << " " << list.get(1) << "!" << std::endl;
std::cout << list.remove(1).get(0) << "!" << std::endl;
std::cout << "count: " << list.count() << std::endl;
std::cout << list.set(0, "goodbye!").get(0) << "!" << std::endl;JavaScript Example
In this example, the browser should open the results in an alert window.
var string = '';
var list = new SinglyLinkedList();
list.insert('world').insert('hello', 0);
string += list.get(0) + ' ' + list.get(1) + '!\r\n';
string += list.remove(1).get(0) + '!\r\n';
string += 'count: ' + list.count() + '\r\n';
string += list.set(0, 'goodbye!').get(0) + '!';
alert(string);Summary
Planning code before writing code is useful for any size project, but is most important in large projects or projects that involve many programmers. Planning before coding helps to reduce the opportunity for bugs by allowing a programmer to conceptualize how code should behave before they start writing. Interfaces help to reduce the amount of bugs and retrofitting that happens on the boundaries of developers' code. Together, these increase the overall stability and quality of the product.
In the case of this entry, the NodeInterface and its derivatives established the contract that List Nodes carry values and positional data; while the ListInterface and its derivatives established the contract that Lists are responsible for manipulating List Nodes. Using these interfaces, we were able to implement Singly Linked Lists in three programming languages in a way that would allow us to replace any component without needing any significant rework of the code.
Code
This entry uses mildly simplified code samples. A more robust version of the code for this entry is available on GitHub:
Related Blog Posts
