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.

hooman734/linkedlist-practice-ts

The Result of The Tests

All the tests passed successfully

Hooman H. - American University of Armenia - Yerevan, Armenia | LinkedIn

Thank you for your time…