Giới thiệu

Là một kiểu dữ liệu gồm đầu (head), đuôi (tail) và độ dài (length)

Linked list gồm nhiều node, 1 node có 1 giá trị và 1 con trỏ trỏ tới node khác hoặc null

Có 2 loại linked list:

• Singly linked list (danh sách liên kết đơn)
• Doubly linked list (danh sách liên kết đôi)

Singly Linked lists (danh sách liên kết đơn)

Khởi tạo

Tạo 1 class cho node của Singly linked list

class NodeSinglyLinkedList {
  val: string;
  next: NodeSinglyLinkedList | null;

  constructor(val: string) {
    this.val = val;
    this.next = null;
  }
}

Tạo 1 class chứa các method của Singly Linked list

class SinglyLinkedList {
  head: NodeSinglyLinkedList | null;
  tail: NodeSinglyLinkedList | null;
  length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  
  push(val){}
  
  pop(){}
  
  unshift(val){}
  
  shift(){}
  
  get(val){}
  
  insert(val, position){}
  
	remove(position){} 
}

Khởi tạo các method

push

  push(val) {
    const newNode = new NodeSinglyLinkedList(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }

pop

  pop() {
    if (!this.head) {
      return undefined;
    }

    let current = this.head;
    let newTail = current;

    while (current.next) {
      newTail = current;
      current = current.next;
    }

    this.tail = newTail;
    this.tail.next = null;

    this.length--;
    return this;
  }

unshift

  unshift(val) {
    const newNode = new NodeSinglyLinkedList(val);

    if (!this.tail) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
    return this;
  }

shift

  shift() {
    if (!this.head) {
      return undefined;
    } else {
      const currentHead = this.head;
      this.head = currentHead.next;
    }

    this.length--;
    return this;
  }

get

  get(position) {
    if (position < 0 || position > this.length) return null;

    let counter = 0;
    let head = this.head;
    while (counter < this.length) {
      if (counter === position) {
        return head;
      }
      head = head.next;
      counter++;
    }
  }

insert

  insert(val, position) {
    if (position < 0 || position > this.length) return null;

    const newNode = new NodeSinglyLinkedList(val);

    if (position === 0) {
      return this.unshift(val);
    }

    if (position === this.length) {
      return this.push(val);
    }

    const prevNode = this.get(position - 1);
    const prevNodeNext = prevNode.next;
    prevNode.next = newNode;
    newNode.next = prevNodeNext;
  }

remove

  remove(position) {
    if (position < 0 || position > this?.length) return null;

    if (position === 0) {
      return this.shift();
    }

    if (position === this.length - 1) {
      return this.pop();
    }

    const currentNode = this.get(position);
    const prevNode = this.get(position - 1);
    prevNode.next = currentNode.next;

    return this;
  }

Doubly Linked lists (danh sách liên kết đôi)

Khởi tạo

Tạo 1 class cho node của Singly linked list

class NodeDoublyLinkedList {
  val: string;
  next: NodeDoublyLinkedList | null;
  prev: NodeDoublyLinkedList | null;

  constructor(val: string) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

Tạo 1 class chứa các method của Singly Linked list

class DoublyLinkedList {
  head: NodeDoublyLinkedList | null;
  tail: NodeDoublyLinkedList | null;
  length: number;

  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  
  push(val){}
  
  pop(){}
  
  unshift(val){}
  
  shift(){}
  
  get(val){}
  
  insert(val, position){}
  
	remove(position){} 
}

Khởi tạo các method

push

  push(val) {
    const newNode = new NodeDoublyLinkedList(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

pop

  pop() {
    if (!this.head) {
      return undefined;
    }

    const newTail = this.tail.prev;
    this.tail.next = null;
    this.tail = newTail;
    this.length--;

    return this;
  }

unshift

  unshift(val) {
    const newNode = new NodeDoublyLinkedList(val);

    if (!this.tail) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length++;
    return this;
  }

shift

  shift() {
    if (!this.head) {
      return undefined;
    } else {
      const currentHead = this.head;
      this.head = currentHead.next;
      this.head.prev = null;
    }

    this.length--;
    return this;
  }

get

  get(position) {
    if (position < 0 || position > this.length) return null;

    let counter = 0;
    let head = this.head;
    while (counter < this.length) {
      if (counter === position) {
        return head;
      }
      head = head.next;
      counter++;
    }
  }

insert

  insert(val, position) {
    if (position < 0 || position > this.length) return null;

    const newNode = new NodeDoublyLinkedList(val);

    if (position === 0) {
      return this.unshift(val);
    }

    if (position === this.length) {
      return this.push(val);
    }

    const currentNode = this.get(position);
    const prevNode = this.get(position - 1);
    prevNode.next = newNode;
    newNode.prev = prevNode;
    newNode.next = currentNode;
    currentNode.prev = newNode;

    this.length++;
    return this;
  }

remove

  remove(position) {
    if (position < 0 || position > this?.length) return null;

    if (position === 0) {
      return this.shift();
    }

    if (position === this.length - 1) {
      return this.pop();
    }

    const prevNode = this.get(position - 1);
    const nextNode = this.get(position + 1);
    prevNode.next = nextNode;
    nextNode.prev = prevNode;

    this.length--;

    return this;
  }

Kết luận

Từ việc triền khai các method ở trên ta có được bảng so sánh độ phức tạp của 2 loại linked list như sau: