Implement a doubly linked list.

Like an array, a linked list is a simple linear data structure. Several

common data types can be implemented using linked lists, like queues,

stacks, and associative arrays.

A linked list is a collection of data elements called *nodes*. In a

*singly linked list* each node holds a value and a link to the next node.

In a *doubly linked list* each node also holds a link to the previous

node.

You will write an implementation of a doubly linked list. Implement a

Node to hold a value and pointers to the next and previous nodes. Then

implement a List which holds references to the first and last node and

offers an array-like interface for adding and removing items:

* `push` (*insert value at back*);

* `pop` (*remove value at back*);

* `shift` (*remove value at front*).

* `unshift` (*insert value at front*);

To keep your implementation simple, the tests will not cover error

conditions. Specifically: `pop` or `shift` will never be called on an

empty list.

If you want to know more about linked lists, check [Wikipedia](https://en.wikipedia.org/wiki/Linked_list).

Go through the setup instructions for Javascript to

install the necessary dependencies:

Install assignment dependencies:

$ npm install

Execute the tests with:

$ npm test

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by

changing `xtest` to `test`.

Classic computer science topic

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

class Node{

constructor(value){

this.value = value;

this.previous = null;

this.next = null;

}

export default class LinkedList{

constructor(){

this.head = null;

this.tail = null;

this.length = 0;

}

// Insert value at back

push(value){

const node = new Node(value);

if(!this.head){

this.head = node;

this.tail = node;

} else{

node.previous = this.tail;

this.tail.next = node;

this.tail = node;

}

this.length++;

}

// Remove value at back

pop(){

if(!this.head) return null;

const previousNode = this.tail.previous;

const oldTailValue = this.tail.value;

if(previousNode){

previousNode.next = null;

this.tail = previousNode;

} else{

this.head = null;

this.tail = null;

}

this.length--;

return oldTailValue;

}

// Remove value at front

shift(){

if(!this.head) return null;

const nextNode = this.head.next;

const oldHeadValue = this.head.value;

if(nextNode){

nextNode.previous = null;

this.head = nextNode;

} else{

this.head = null;

this.tail = null;

}

this.length--;

return oldHeadValue;

}

// Insert value at front

unshift(value){

const node = new Node(value);

if(!this.head){

this.head = node;

this.tail = node;

} else{

this.head.previous = node;

node.next = this.head;

this.head = node;

}

this.length++;

}

/*

delete(value){

if(this.head.value == value){

this.shift();

} else if(this.tail.value == value){

this.pop();

} else {

let currentNode = this.head.next;

while(true){

if(currentNode == null) break;

if(currentNode.value == value){

currentNode.next.previous = currentNode.previous;

currentNode.previous.next = currentNode.next;

currentNode.previous = null;

currentNode.next = null;

this.length--;

break;

} else{

currentNode = currentNode.next;

}

}

}

}

// Number of values in doubly linked list

count(){

return this.length;

}

import LinkedList from './linked-list';

describe('LinkedList', () => {

test('add/extract elements to the end of the list with push/pop', () => {

const list = new LinkedList();

list.push(10);

list.push(20);

expect(list.pop()).toBe(20);

expect(list.pop()).toBe(10);

});

test('extract elements from the beginning of the list with shift', () => {

const list = new LinkedList();

list.push(10);

list.push(20);

expect(list.shift()).toBe(10);

expect(list.shift()).toBe(20);

});

test('add/extract elements from the beginning of the list with unshift/shift', () => {

const list = new LinkedList();

list.unshift(10);

list.unshift(20);

expect(list.shift()).toBe(20);

expect(list.shift()).toBe(10);

});

test('unshift/pop', () => {

const list = new LinkedList();

list.unshift(10);

list.unshift(20);

expect(list.pop()).toBe(10);

expect(list.pop()).toBe(20);

});

test('example', () => {

const list = new LinkedList();

list.push(10);

list.push(20);

expect(list.pop()).toBe(20);

list.push(30);

expect(list.shift()).toBe(10);

list.unshift(40);

list.push(50);

expect(list.shift()).toBe(40);

expect(list.pop()).toBe(50);

expect(list.shift()).toBe(30);

});

test('can count its elements', () => {

const list = new LinkedList();

expect(list.count()).toBe(0);

list.push(10);

expect(list.count()).toBe(1);

list.push(20);

expect(list.count()).toBe(2);

});

test('sets head/tail after popping last element', () => {

const list = new LinkedList();

list.push(10);

list.pop();

list.unshift(20);

expect(list.count()).toBe(1);

expect(list.pop()).toBe(20);

});

test('sets head/tail after shifting last element', () => {

const list = new LinkedList();

list.unshift(10);

list.shift();

list.push(20);

expect(list.count()).toBe(1);

expect(list.shift()).toBe(20);

});

test('deletes the element with the specified value from the list', () => {

const list = new LinkedList();

list.push(10);

list.push(20);

list.push(30);

list.delete(20);

expect(list.count()).toBe(2);

expect(list.pop()).toBe(30);

expect(list.shift()).toBe(10);

});

test('deletes the only element', () => {

const list = new LinkedList();

list.push(10);

list.delete(10);

expect(list.count()).toBe(0);

});

test('deletes the first of two elements', () => {

const list = new LinkedList();

list.push(10);

list.push(20);

list.delete(10);

expect(list.count()).toBe(1);

expect(list.pop()).toBe(20);

});

test('deletes the second of two elements', () => {

const list = new LinkedList();

list.push(10);

list.push(20);

list.delete(20);

expect(list.count()).toBe(1);

expect(list.pop()).toBe(10);

});

test('delete does not modify the list if the element is not found', () => {

const list = new LinkedList();

list.push(10);

list.delete(20);

expect(list.count()).toBe(1);

});