2
\$\begingroup\$

This is my Singly Linked List implementation in ES6.

class LinkedList{

    constructor(){
        this.head = null;
        this.size = 0;
    }

    insert(item){
        this.size ++;
        let p = new Node(item);
        if(this.head === null){
            this.head = p;
        }
        else{
           p.next = this.head;
           this.head = p;
        }
    }
    insertAt(item, index){
        if(index > this.size){
            throw "Wrong index";
        }
        let p = new Node(item);
        if(index === 0){
            p.next = this.head;
            this.head = p;
            return;
        }
        let curr = this.head;
        while(curr !== null){
            if(index === 0){
                if(curr.next === null){
                    curr.next = p;
                    return;
                }
                else if(curr.next.next === null){
                    curr.next = p;
                }else{
                    curr.next.next = p.next;
                    curr.next = p;

                }
                return;
            }
            curr = curr.next;
            index --;
        }

    }
    remove(item){
        let curr, prev;
        prev = curr = this.head;
        if(item === curr.val){
            this.head = this.head.next;
            this.size --;
            return;
        }
        while(curr !== null){
            if (curr.val === item){
                prev.next = curr.next;
                this.size --;
                return;
            }
            prev = curr;
            curr = curr.next;

        }
        throw "Item doesn't exist in list."
    }
    length(){
        return this.size;
    }

    is_empty(){
        return this.size === 0;
    }
    printList(){
        let curr = this.head;
        let out = [];
        while(curr !== null){
            if(curr.next === null){
                out.push(curr.val);
            }else{
                out.push(curr.val);
                out.push("->")
            }
            curr = curr.next;
        }
        return out.join("");
    }
}
class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

const list = new LinkedList();
list.insert(12);
list.insert(9);
list.insert(13);
list.insert(17);
console.log(list.printList());
list.remove(12);
console.log(list.printList());
console.log(list.length());
console.log(list.is_empty());
list.insertAt(21, 2);
console.log(list.printList());

Invite reviews please on all fronts, improvements, modern usage of JS. Thanks.

\$\endgroup\$
3
\$\begingroup\$

TL;DR

  • Style could better adhere to established standards.
  • insertAt has bugs to resolve.
  • This class is missing basic add/remove functions which prevent it from being useful.
  • Writing a linked list class in JS only makes sense from an educational standpoint; primitive arrays are efficient, universal and offer more functionality with less code.

Style

Spacing

  • Use a space between )s, {s and keywords, e.g.

    if(this.head === null){ 
    

    is cleaner as

    if (this.head === null) {
    
  • Add vertical spacing between lines to group logical code blocks together and separate loop, conditional and function logic from declarations. For example,

    let curr = this.head;
    while(curr !== null){
    

    is easier to read as

    let curr = this.head;
    
    while (curr !== null) {
    
  • this.size ++ is clearer as this.size++.

  • Be consistent--sometimes you use }else{, and sometimes you use

    }
    else{
    
  • Your whitespace fixes can be done by putting the code into SE's Code Snippet and pressing "Tidy", then adding blank lines around blocks by hand. Generally, I don't see reason to deviate from this prescribed style.

Variable and function naming

  • Function names switch between snake_case and camelCase. All JS naming should be camelCase, except class names, which are UpperCamelCase (as you use).
  • Avoid single-letter variable names like p unless the meaning is obvious. In this case, something like newNode might be clearer.

Functionality

Errors

  • throw "Wrong index"; is an unclear error message. What exactly is wrong with the index? Consider throw "Index out of list bounds"; which more accurately describes the problem.
  • You may wish to reconsider using errors at all. I find throwing errors in JS generally less appropriate than return values because the calling code can stick to normal conditionals to handle control flow.

    Also, not throwing errors is in keeping with JS's builtin library functions, which generally don't complain about invalid or missing input. For insertAt, for example, you could return true if the insertion was successful and false otherwise. If the user provides something silly as an index that causes a crash, they'll get an appropriate stack trace that likely explains the problem better than a hand-written error string.

    If you do wish to stick with error throwing, ensure it is comprehensive. For example, if (index > this.size) doesn't handle the case when index < 0 which could result in difficult-to-track-down bugs for the client who has to make design assumptions based on your throw.

    Then, once you've covered that scenario, it begs the question whether you should now validate that the provided input is an integer number and throw an error message for that as well.

    The point is, adding errors gives the client the illusion of a comprehensive and robust set of argument and function state restrictions, which is problematic if they aren't actually robust. Throwing no errors, assuming the client is behaving, and reporting true/false as to whether some function failed or not seems preferential.

Variable keywords

  • Use const when appropriate in place of let. This should apply to almost everything except for loop counters, accumulator variables and runner nodes. For example, let out = []; should be const out = [];. Even if the risk of bugs caused by accidental reassignment is low, this has semantic benefits.

Misleading function names

  • printList() is a misleading name; it stringifies the list rather than printing. I recommend overriding toString() here.
  • insert() usually refers to insertion at some specific element, which is the behavior your insertAt() function offers. With insert(), It's not obvious where the insertion is happening; one of addFront, unshift or push seem clearer, depending on which end of your list you decide the front to be.

Internal logic

  • insertAt is not working correctly, placing items incorrectly, not at all, and neglecting to increment the size.
  • Consider adjusting your insertAt code to avoid using returns and curr.next.next, which is difficult to reason about and causing bugs.
  • In printList, pains are taken to conditionally add the -> arrow only for non-last elements when you can simply walk the list and use out.join("->").
  • Since your internal code relies only on Node objects, you can make your code cleaner by testing while (curr) instead of while (curr === null). This is debatable, because it restricts your internal logic from distinguishing between null and undefined or other falsey values, but if you trust yourself to be consistent about it, I prefer the cleaner look.

Interface

  • As written, I find your provided function interface insufficient for typical linked list needs. It's not obvious what functionality this class offers over, say, a primitive array.

    Consider remove(item). This sort of function that takes an element and searches the structure for it is best used for hashes with random access. The whole point of linked lists is to offer fast insertion and removal of front and back elements, regardless of what those elements might be. Anything in the middle is of no concern, and libraries that offer access to these elements, such as Java's LinkedList collection are generally considered to be flawed because clients may make false assumptions about the time complexity of provided operations.

    Without constant time front and back adds, removals and peeks, I can't foresee a reason to use this class instead of a primitive array. insert is the only useful linked list function your interface offers (disregarding isEmpty, printList, etc as useful but trivial).


Rewrites

Revision #1 (same functionality)

class LinkedList {
  constructor() {
    this.head;
    this.size = 0;
  }

  addFront(value) {
    const newNode = new Node(value);
  
    if (this.head) {
      newNode.next = this.head;
    } 
    
    this.head = newNode;
    this.size++;
  }
  
  insertAt(value, idx) {
    let curr = this.head;
    let prev;
    
    while (curr && idx > 0) {
      prev = curr;
      curr = curr.next;
      idx--;
    }
    
    if (prev) {
      prev.next = new Node(value);
      prev.next.next = curr;
      this.size++;
    }
    else {
      this.addFront(value);
    }    
  }
  
  remove(value) {
    let curr = this.head;
    let prev;
    
    while (curr) {
      if (curr.val === value) {
        if (prev) {
          prev.next = curr.next;
        }
        else {
          this.head = undefined;
        }
        
        this.size--;
        return true;
      }
      
      prev = curr;
      curr = curr.next;
    }
    
    return false;
  }
  
  length() {
    return this.size;
  }

  empty() {
    return !this.size;
  }
  
  toString() {
    const result = [];
    let curr = this.head;

    while (curr) {
      result.push(curr.val);
      curr = curr.next;
    }
    
    return result.join("->");
  }
}

class Node {
  constructor(val, nextNode=null) {
    this.val = val;
    this.next = nextNode;
  }
}

const list = new LinkedList();
list.remove(1123);
list.insertAt(21, 33);
list.remove(21);
list.addFront(12);
list.addFront(9);
list.addFront(13);
list.addFront(17);
list.remove(1123);
console.log(list.toString());
list.remove(12);
console.log(list.toString());
console.log(list.length(), list.empty());
list.insertAt(21, 2);
console.log(list.toString(), list.length());
list.insertAt(11, 0);
console.log(list.toString(), list.length());

Revision #2 (added front/back operations)

class LinkedList {
  constructor() {
    this.head;
    this.tail;
  }

  addFront(value) {
    const newHead = new Node(value);
  
    if (this.head) {
      newHead.next = this.head;
    } 
    else {
      this.tail = newHead;
    }
    
    this.head = newHead;
  }
  
  addBack(value) {
    if (this.tail) {
      this.tail.next = new Node(value);
      this.tail = this.tail.next;
    }
    else {
      this.head = this.tail = new Node(value);
    }
  }
  
  peekFront() {
    return this.head ? this.head.val : null;
  }
  
  peekBack() {
    return this.tail ? this.tail.val : null;
  }
  
  popFront() {
    if (this.head) {
      const value = this.head.val;
      this.head = this.head.next;
      
      if (!this.head) {
        this.tail = null;
      }
      
      return value;
    }
  }
    
  empty() {
    return !this.head;
  }
  
  toString() {
    const result = [];
    let curr = this.head;

    while (curr) {
      result.push(curr.val);
      curr = curr.next;
    }
    
    return result.join("->");
  }
}

class Node {
  constructor(val, nextNode=null) {
    this.val = val;
    this.next = nextNode;
  }
}

const list = new LinkedList();
list.popFront();
console.log(list.toString(), list.empty());
list.addBack(1);
console.log(list.toString(), list.empty());
list.popFront();
console.log(list.toString(), list.empty());
list.addFront(2);
console.log(list.toString());
list.addBack(3);
console.log(list.toString());
list.popFront();
console.log(list.toString());
list.addFront(4);
list.addBack(5);
console.log(list.toString());

Note that there is no popBack() because this operation would be linear without doubly linked nodes. However, the class is sufficient to support both stacks and queues with all operations in constant time. Without the tail pointer, only a stack could be supported. Adding popBack() and double links would give you a deque class.

Revision #3 (supported a queue)

class Queue {
  constructor() {
    this.list = new LinkedList();
  }
  
  offer(value) {
    this.list.addBack(value);
  }
  
  poll() {
    return this.list.popFront();
  }
  
  peek() {
    return this.list.peekFront();
  }
  
  empty() {
    return this.list.empty();
  }
  
  toString() {
    return this.list.toString();
  }
}

class LinkedList {
  constructor() {
    this.head;
    this.tail;
  }

  addFront(value) {
    const newHead = new Node(value);
  
    if (this.head) {
      newHead.next = this.head;
    } 
    else {
      this.tail = newHead;
    }
    
    this.head = newHead;
  }
  
  addBack(value) {
    if (this.tail) {
      this.tail.next = new Node(value);
      this.tail = this.tail.next;
    }
    else {
      this.head = this.tail = new Node(value);
    }
  }
  
  peekFront() {
    return this.head ? this.head.val : null;
  }
  
  peekBack() {
    return this.tail ? this.tail.val : null;
  }
  
  popFront() {
    if (this.head) {
      const value = this.head.val;
      this.head = this.head.next;
      
      if (!this.head) {
        this.tail = null;
      }
      
      return value;
    }
  }
    
  empty() {
    return !this.head;
  }
  
  toString() {
    const result = [];
    let curr = this.head;

    while (curr) {
      result.push(curr.val);
      curr = curr.next;
    }
    
    return result.join("->");
  }
}

class Node {
  constructor(val, nextNode=null) {
    this.val = val;
    this.next = nextNode;
  }
}

const q = new Queue();
q.offer(1);
console.log(q.poll());
console.log(q.poll());

for (let i = 0; i < 5; i++) {
  q.offer(i);
}

while (!q.empty()) {
  console.log(q.poll());
}

After all that work, a benchmark shows that it's no faster than a primitive array. This is likely due to overhead from object creation, function calls and garbage collection, which counteracts the shifting necessary on the primitive array.

\$\endgroup\$
  • 1
    \$\begingroup\$ A delight to read! Dear OP, Look into iterators. That would enable forEach coding. Also Blindman76 warning of lack of private variables in class is notable. You really want to protect clients from themselves and make sure the linkedList can be used only as intended. \$\endgroup\$ – radarbob Jan 14 at 0:29
0
\$\begingroup\$

Unsafe and unusable.

Class syntax is dangerous

The class syntax encourages you to expose the objects state, this means it can mutate outside your control.

New developments allow class to have private properties. #privateNamed the hash means private. However its implementations is an abomination to the languages, we now have a situation where access type is embedded in the variable name. Names should be independent of any language constructs. Anyways I digress...

As it stands your object (class) is unsafe, you expose head and size (in LinkedList) and next (in Node) meaning that outside code can deliberately or by accident mutate the objects state such that your function becomes inoperable.

It is possible for your code to indefinitely block the page, meaning that the only way to fix the problem is for the page to crash or it to be forced to close.

Mutation examples

const list = new LinkedList()
list.insert("😧");
list.head.next = list.head;  // cyclic link. 
list.remove("☠"); // Untrappable page blocking error
list.printList(); // will crash the page with out of memory error

const list = new LinkedList()
list.size = "🙈🙉🙊";
console.log(list.length); // >> "🙈🙉🙊" nonsense 


const list = new LinkedList()
list.insert("A");
const a = list.head;
list.insert("B");
const b = list.head;
list.insert("C");
list.insert("D");
const d = list.head;    
b.next = d;  // removes c 

console.log(list.length()); // >> 4 Incorrect
var node = a;
for(let i = 0; i < list.length; i++){
    console.log(node.value); // WTF throws error on 4th iteration
    node = node.next;
}

Normal use errors

const list = new LinkedList()
list.insert("A");         
list.insertAt("B", -1);  // does not insert returning undefined.


const list = new LinkedList()
list.size = 100; 
console.log(list.is__Empty()); // >> false, wrong answer the list is empty

I could go on, there are many dangers when you expose internal state. Programmers, you included will be tempted to use a shortcuts, or accidently mutate the list with catastrophic consequences.

I would never allow such a dangerous object into a project, it is unusable because of its dangerous behaviour.

Object factories

Consider using a factory to create your Object.

Factories let you create a private state via closure that can not be mutate. You can confidently use the state because it is hidden and immutable.

Factory example.

The factory returns a frozen object with the state hidden via closure. I add to functions. Iterator LinkedList.values to iterate the list from 0 to size-1 eg console.log([...list.values()]) will list items as an array. Also linkedList.itemAt(index) as the linked list is useless without them.

You do not get access to nodes, only the values they contain. And printList is called toString

Note code is untested and as an example only. May contain typos or logic errors.

function LinkedList() {
    var head, size = 0;
    const add = (value, next) => {
        size ++;
        return {value, next};
    }
    const vetIndex = idx => isNaN(idx) || idx > size || idx < 0;
    const list = Object.freeze({
        get length() { return size },
        get isEmpty() { return size === 0 },
        insert(item) { head = add(item, head) },
        insertAt(item, idx = 0) {
            if (vetIndex(idx)) { throw new RangeError("Bad index") }
            if (idx === size) { head = add(item, head) } 
            else {
                let curr = head;
                while (++idx < size) { curr = curr.next }
                curr.next = add(item, curr.next);
            }
        },
        remove(item) {
            if (head.value === item) { 
                head = head.next;
                size --;
            } else {
                let curr = head;
                while (curr && curr.next && curr.next.value !== item) { curr = curr.next }
                if (curr) {
                    curr.next = curr.next ? curr.next.next : undefined;
                    size --;
                }
            }
        },
        toString() {
            var str = "";
            if (size) {
                str += head.value;
                let curr = head.next;
                while (curr) {
                    str += "->" + curr.value;
                    curr = curr.next;
                }
            }
            return str;
        },  
        *values() {
            var idx = 0;
            while (idx < size) { yield list.itemAt(idx++) }
        },
        itemAt(idx) {
            if (size && !vetIndex(idx)) {
                vetIndex(idx);
                if (idx === size) { return head.value }
                else {
                    let curr = head;
                    while (++idx < size) { curr = curr.next }
                    return curr.value
                }
            }
        },            
    });
    return list;
}

Some more points on your code

  • Function scope variables should be declared as var. Show you understand the language and use the correct declaration type.
  • Use const for constants. Eg in printList you define an array let out = []; out is a reference to an array, the reference never changes, only the content of the array does, so use a constant const out = [];
  • Only throw if not doing so will damage state such that continuing will create undefined behaviours. You threw if an item could not be found in remove There is no reason to throw as it does not damage your state. Return undefined and let the calling function deal with their problems.
  • When you throw do not throw strings (many catches assume an object and rethrow if its just a string). Use appropriate error objects. eg you throw a string throw "Wrong index"; you should throw an error throw new RangeError("Bad index"); Or throw new Error("Bad index");
  • Don't add redundant code. the function insertAt has 3 returns yet can be written with on extra else and a break, with no return tokens.
  • Don't use null, its undefined if not defined.
  • Always use the shorts form. Eg if(this.head === null) use if(!this.head) and if (!curr.next) { curr.next = p;} else if (!curr.next.next) { curr.next = p;} becomes if(!curr.next || !curr.next..next) { curr.next = p }
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.