fabianuribe.com/ blog

Data Structures in Javascript: Linked Lists

A Linked List is a sequence of nodes, it can be single linked or double linked. Nodes on a single linked lists have a reference to their successor, on doubly linked lists each node also has a reference to their predecessor.

The implementation

To make the basic operations simpler, every instance of the Doubly Linked List will hold a reference to the first and last elements in the list, it will also keep track of the number of nodes it holds.

The linked list will implement the following basic operations :

The complete source code for data structure’s including the unit tests for this implementation are included here.

Complexity

Operation Complexity
Search O(n)
Insert O(1)
Delete O(1)
Max/Min O(n)
Predecessor O(1)
Successor O(1)

The Good

The Bad