Month: December 2018

Linked list là 1 dạng cấu trúc dữ liệu mà mỗi phần tử trong đó sẽ liên kết với phần tử đứng đằng sau nó. Do tính chất của cấu trúc nên việc truy xuất 1 phần tử thông qua index cụ thể sẽ chậm hơn so với mảng vì Linked list phải loop thông qua các phần tử bắt đầu từ begining (head) cho đến khi tìm được phần tử đó

Implement:

B1: Khởi tạo node với 2 thuộc tính là value và next:

B2: Viết hàm push

    push(value) {
      const node = createNode(value);

      if (this.length === 0) {
        this.head = node;
        this.tail = node;
        this.length++;
        return node;
      }

      this.tail.next = node;
      this.tail = node;
      this.length++;
    }

B3: Viết hàm pop

    pop() {
      if (this.isEmpty()) {
        return null;
      }
      if (this.head === this.tail) {
        this.head = null;
        this.tail = null;
        this.length--;
        return null;
      }

      let current = this.head;
      let penultimate;

      while (current) {
        if (current.next === this.tail) {
          penultimate = current;
          break;
        }
        current = current.next;
      }

      penultimate.next = null;
      this.tail = penultimate;
      this.length--;
    }

B4: Viết hàm get

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

      if (index === 0) {
        return this.head;
      }

      let current = this.head;
      let i = 0;
      while (i < index) {
        i++;
        current = current.next;
      }
      return current;
    }

B5: Viết hàm delete

    delete(index) {
      if (index < 0 || index > this.length) {
        return null;
      }
      if (index === 0) {
        let deleted = this.head;
        this.head = deleted.next;
        this.length--;
        return deleted;
      }

      let current = this.head;
      let previous;
      let i = 0;

      while (i < index) {
        i++;
        previous = current;
        current = current.next;
      }
      let deleted = current;
      previous.next = current.next;
      this.length--;
      return deleted;
    }

Full code

function createNode(value) {
  return {
    value,
    next: null
  };
}

function createLinkedList() {
  return {
    head: null,
    tail: null,
    length: 0,
    isEmpty() {
      return this.length === 0;
    },
    push(value) {
      const node = createNode(value);

      if (this.length === 0) {
        this.head = node;
        this.tail = node;
        this.length++;
        return node;
      }

      this.tail.next = node;
      this.tail = node;
      this.length++;
    },
    pop() {
      if (this.isEmpty()) {
        return null;
      }
      if (this.head === this.tail) {
        this.head = null;
        this.tail = null;
        this.length--;
        return null;
      }

      let current = this.head;
      let penultimate;

      while (current) {
        if (current.next === this.tail) {
          penultimate = current;
          break;
        }
        current = current.next;
      }

      penultimate.next = null;
      this.tail = penultimate;
      this.length--;
    },
    get(index) {
      if (index < 0 || index > this.length) {
        return null;
      }

      if (index === 0) {
        return this.head;
      }

      let current = this.head;
      let i = 0;
      while (i < index) {
        i++;
        current = current.next;
      }
      return current;
    },
    delete(index) {
      if (index < 0 || index > this.length) {
        return null;
      }
      if (index === 0) {
        let deleted = this.head;
        this.head = deleted.next;
        this.length--;
        return deleted;
      }

      let current = this.head;
      let previous;
      let i = 0;

      while (i < index) {         i++;         previous = current;         current = current.next;       }       let deleted = current;       previous.next = current.next;       this.length--;       return deleted;     },     print() {       let arr = [];       let current = this.head;       while (current) {         arr.push(current.value);         current = current.next;       }       return arr.join("=>");
    }
  };
}

Link tham khảo: https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm

Stack là 1 dạng cấu trúc dữ liệu tuân theo nguyên tắc LIFO ( Last in First out).
Giống như chồng bát dĩa, chúng ta phải lấy cái dĩa trên cùng trước khi muốn lấy những cái ở phía dưới.

Ví dụ minh họa:

Các hàm và thuộc tính cơ bản của Stack:

• POP
• PUSH
• isEmpty
• peek
• length

Implement

function createStack() {
  const stack = [];

  return {
    push(item) {
      stack.push(item);
    },
    pop() {
      stack.pop();
    },
    peek() {
      return stack[stack.length - 1];
    },
    get length() {
      return stack.length;
    },
    isEmpty() {
      return stack.length === 0;
    }
  };
}

Link tham khảo: https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm