In this post I will implement one of the most fundamental data structure in computer science – linked list. Linked list – is a dynamic sequence of linked nodes where each node composed of a datum and a reference to the next node. Lists, stacks, queues and many other data types can be implemented using linked list. There are several types of linked lists:

In this post I will implement the most frequent type – singly linked list. Let’s start with the definition of node:

Usually linked list has following functions:

  • isEmpty() – to check whether the list is empty or not
  • length() – to get the number of nodes in the list
  • find() – to find existing node by value
  • addAfter(), addBefore() – to add new node after / before the specified node
  • remove() – to remove existing node In more advance cases linked list can also have functions:

  • addFirst(), addLast() - to add new node at given position
  • removeFirst(), removeLast() - to remove existing node at given position
  • reverse() – to reverse existing nodes
  • copy() – to create deep copy of the existing list
  • merge() – to merge given list with the current one

Instead of the specific functions addFirst(), addLast(), removeFirst() and removeLast() I will implement more generic addFromStart(), addFromEnd(), removeFromStart() and removeFromEnd(), where one can specify the exact position a node has to be added or removed. Also it’s worth mentioning, that my implementation heavily relies on a notion of a dummy (or sentinel) node.