Алгоритмы. Списки со ссылками (Linked List).

linkedList.md

LinkedList is made of a bunch of nodes that point to the next one in the list. Every node in a LinkedLists has two properties, the value of whatever is being store and a pointer to the next node in the list.

LinkedLists have their ups and downs. On one hand, adding and removing is a breeze: you just have the change the next pointer on the previous node and that's it. Getting is a pain though: if .get is called you have to loop through the nodes until you get to the right node. And that's the tradeoff between LinkedList and ArrayList: LinkedList's adds and deletes are O(1) but the gets are O(n); ArrayList's adds and deletes are O(n) but the gets are O(1). So which one is better? It depends! If you're doing a bunch of adds and deletes but not many gets, stick to LinkedLists. Doing a bunch of gets? ArrayLists. Both? You decide!

Let's dissect a delete.

value: [a] [b] [c] [d] next: [ ]-> [ ]-> [ ]-> [ ]-> null

-> delete is called on index 2 (value 'c') -> grab the head (value 'a') -> loop through the nexts until you get the index before the one to be deleted (value 'b') -> change the the next of index 1 to be the next of index 2 -> decrement length -> return the value of the deleted node

class LinkedList {
  constructor() {
    this.tail = this.head = null;
    this.length = 0;
  }
  
  push(value) {
    const node = new Node(value);
    this.length++;
    
    if (this.head) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
  }
  
  pop() {
    if (!this.head) return null;
    if (this.head === this.tail) {
      const {value} = this.head;
      this.head = this.tail = null;
      return value;
    }
    
    const penultimate = this._find(null, (value, nodeValue, i, current) => current.next === this.tail);
    const {value} = penultimate.next;
    penultimate.next = null;
    this.tail = penultimate;
    this.length--;
    return value;
  }
  
  _find(value, test = this.test) {
    let current = this.head;
    let i = 0;
    
    while(current) {
      if (test(value, current.value, i, current)) {
        return current;
      }
      current = current.next;
      i++;
    }
    
    return null;
  }
  
  get(index) {
    const node = this._find(index, this.testIndex);
    return node ? node.value || null;
  }
  
  delete(index) {
    if (index === 0) {
      const head = this.head;
      this.head = head ? head.next : null;
      this.length--;
      return head.value;
    }
    
    const node = this._find(index - 1, this.testIndex);
    const excise = node.next;
    if (!excise) return null;    
    node.next = excise.next;    
    if (!node.next.next) this.tail = node.next;
    this.length--;
    return excise.value;
  }
  
  test(search, nodeValue) {
    return search === nodeValue;
  }
  
  testIndex(search, __, i) {
    return search === i;
  }
  
  serialize() {
    const ans = [];
    let current = this.head;
    if (!current) return ans;
    while (current) {
      ans.push(current.value);
      current = current.next;
    }
    return ans;
  }
}

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// unit tests
// do not modify the below code
describe('LinkedList', function() {
  const range = length => Array.apply(null, {length: length}).map(Number.call, Number);
  const abcRange = length => range(length).map( num => String.fromCharCode( 97 + num ) );
  let list;
  
  beforeEach( () => {
    list = new LinkedList();
  })
  
  it('constructor', () => {
    expect(list).toEqual(jasmine.any(LinkedList));
  });
  
  it('push', () => {
    abcRange(26).map( character => list.push(character) );
    expect(list.length).toEqual(26);
  });
  
  it('pop', () => {
    abcRange(13).map( character => list.push(character) );
    expect(list.length).toEqual(13);
    range(10).map( () => list.pop() );
    expect(list.length).toEqual(3);
    expect(list.pop()).toEqual('c');
  });
  
  it('get', () => {
    list.push('first');
    expect(list.get(0)).toEqual('first');
    list.push('second');
    expect(list.get(1)).toEqual('second');
    expect(list.get(0)).toEqual('first');
    abcRange(26).map( character => list.push(character));
    expect(list.get(27)).toEqual('z');
    expect(list.get(0)).toEqual('first');
    expect(list.get(9)).toEqual('h');
    list.pop();
    expect(list.get(list.length-1)).toEqual('y');
  });
  
  it('delete', () => {
    abcRange(26).map( character => list.push(character) );
    list.delete(13);
    expect(list.length).toEqual(25);
    expect(list.get(12)).toEqual('m');
    expect(list.get(13)).toEqual('o');
    list.delete(0);
    expect(list.length).toEqual(24);
    expect(list.get(0)).toEqual('b');
  });
});