Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A simple linked list implemented in JavaScript
const LinkedList = function() {
this.head = null;
this.tail = null;
};
LinkedList.prototype.addToTail = function(value) {
const newTail = { value, next: null };
if (this.tail) {
this.tail.next = newTail;
} else {
this.head = newTail;
}
this.tail = newTail;
};
LinkedList.prototype.removeHead = function() {
const currentHead = this.head;
const newHead = this.head.next;
if (newHead === null) {
this.tail = null;
}
this.head = newHead;
return currentHead ? currentHead.value : null;
};
LinkedList.prototype.contains = function(target) {
let node = this.head;
while (node) {
if (node.value === target) {
return true;
}
node = node.next;
}
return false;
};
const list = new LinkedList();
// console.assert(list.tail === null);
// console.assert(list.head === null);
// list.addToTail(4);
// list.addToTail(5);
// console.assert(list.head.value === 4);
// console.assert(list.contains(5) === true);
// console.assert(list.contains(6) === false);
// console.assert(list.removeHead() === 4);
// console.assert(list.tail.value === 5);
// console.assert(list.removeHead() === 5);
// console.assert(list.removeHead() === null);
// console.assert(list.tail === null);
// console.assert(list.head === null);
for (let i = 0; i < 250000000; i++) {
list.addToTail(i);
}
console.log(list.contains(300000));
@spl

This comment has been minimized.

Copy link

spl commented Jan 28, 2019

See my bug report on removeHead(). To summarize, this is problematic:

const list = new LinkedList();
list.removeHead();
/*
Uncaught TypeError: Cannot read property 'next' of null
    at LinkedList.removeHead (<anonymous>:3:29)
    at <anonymous>:1:6
*/

A better implementation first checks if this.head is null:

LinkedList.prototype.removeHead = function() {
  if (this.head) {
    const oldValue = this.head.value;
    const newHead = this.head.next;
    if (newHead === null) {
      this.tail = null;
    }
    this.head = newHead;
    return oldValue;
  } else {
    return null;
  }
};

This implementation also resembles its Rust counterpart much more closely:

pub fn remove_head(&mut self) -> Option<i32> {
    if let Some(head) = &mut self.head {
	let old_value = Some(head.value);
	let new_head = head.next.take();
	if new_head.is_none() {
	    self.tail = None;
	};
	self.head = new_head;
	old_value
    } else {
	None
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.