Implementing four types of linked-lists

Introduction

I recently have developed four types of linked-lists, namely:

  • singly-linked-list — the simplest member of the linked-lists family, with a head and null as the next field of the tail node
  • doubly-linked-list — like the singly-linked-list, but each node has access to its previous neighbor in addition to its next neighbor
  • circular-singly-linked-list — exactly identical to the singly-linked-list but in contrast to that, its tail has access to its head instead of null and forms a circle
  • circular-doubly-linked-list — exactly identical to the doubly-linked-list though the tail node has access to the head and makes it like a circle

My approach was, TDD (test-driven development). In that manner, I first appropriated the overall necessary tests to measure whether my upcoming developments meet all the requirements and what anticipated from the functionality of the functions for the total linked-lists or not.

I used TypeScript programming language and Webstorm IDE for this purpose and the workflow went as following.

Start Point

I initiated with composing the interface of the linked-list class that I called it ICollection as follows:

Second Point

As the development started with making up the ICollection, the interface of all linked-lists which was the first level of the abstraction concept, the next level of abstraction before the eventual implementation is having an abstract class in between.

To do that, I abstracted out all the generic functionality of the entire linked-lists through the AbstractCollection class.

By calling generic functionality, I meant, it does not belong to a specific type of linked-list, and therefore, to implement it we do not rely on how a particular linked-list got implemented which in turn, lets us to put them in one level backward of the actual implementation of linked-lists.

Here you can find its implementation:

This level of abstraction helps us to stay away from the complexity and specialty of each individual linked-list structure. It means the responsibility of tracking of some identifiers like the ‘head’, ‘tail’, and ‘size’ of each linked-list leaves for the most-inner implementation.

As such, we can finally code all fairly unique implementations of linked-lists individually, for instance, doubly-linked-list does have a ‘prev’ identifier whereas singly-linked-list does not, and also pursuing some identifiers such as ‘head’, ‘tail’, and ‘size’.

Due to the fact that my ICollection interface has an anonymous iterator.

[Symbol.iterator]() : Iterator<T>;

function that returns the Iterator of type T, so that, it makes me open to use the Iterator functionality of the built-in Iterator of TypeScript.

Firstly, I used Array.from to convert iterator to an array.

Array.from(this)

Then easily I used it to implement all the functions inside the AbstractCollection class, completely remaining in the abstraction level. For example in the underneath function, I just used this built-in function to implement contains().

contains(value: T): boolean {
return this.toArray().includes(value);
}

Third Point

Finally, I implemented all the linked-list with their unique and distinct structures together with the rest functions or methods:

  • add()
  • clear()
  • reverse()

These functions needed to be coded inside of each type of linked-list individually.

For the sake of brevity, I did not put the remained Gists. Please find the Repository of my code here.

The Result of The Tests

All the tests passed successfully

Thank you for your time…

Graduate Alumni from AUA

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store