알고리즘 문제 풀며 배우거나 강의를 통해 배운 걸 토대로 정리 중..

linear data structure

linked list

단일 연결 리스트

각 노드가 데이터와 포인터를 가지며, “한 줄”로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

function Node(data) {
  this.data = data;
  this.next = null;
}

function LinkedList() {
  this.head = null;
  this.length = 0;
}

LinkedList.prototype.size = function () {
  return this.length;
};
LinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};
LinkedList.prototype.printNode = function () {
  let print = "";

  for (let node = this.head; node != null; node = node.next) {
    print += `${node.data} -> `;
  }
  print += "null";

  console.log(print);
};
LinkedList.prototype.append = function (data) {
  let newNode = new Node(data),
    current = this.head;

  if (this.head === null) {
    this.head = newNode;
  } else {
    while (current.next != null) {
      current = current.next;
    }
    current.next = newNode;
  }
  this.length++;
};
LinkedList.prototype.insert = function (data, position = 0) {
  if (position < 0 || position > this.length) {
    return false;
  }

  let newNode = new Node(data),
    current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    newNode.next = current;
    this.head = newNode;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }
    newNode.next = current;
    prev.next = newNode;
  }
  this.length++;

  return true;
};
LinkedList.prototype.remove = function (data) {
  let current = this.head,
    prev = current;

  while (current.data != data && current.next != null) {
    prev = current;
    current = current.next;
  }

  if (current.data != data) {
    return null;
  }

  if (current === this.head) {
    this.head = current.next;
  } else {
    prev.next = current.next;
  }

  this.length--;

  return current.data;
};
LinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    return null;
  }

  let current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    this.head = current.next;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }
    prev.next = current.next;
  }
  this.length--;

  return current.data;
};
LinkedList.prototype.indexOf = function (data) {
  let current = this.head,
    index = 0;

  while (current != null) {
    if (current.data === data) {
      return index;
    }
    index++;
    current = current.next;
  }
  return -1;
};

const ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.insert(100);
ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode();

console.log(ll.indexOf(1000)); // -1 (없으면 -1 반환)
console.log(ll.indexOf(1)); // 4
console.log(ll.indexOf(100)); // 0
console.log(ll.indexOf(10)); // 2

console.log(ll.remove(100)); // 100
ll.printNode(); // 2 -> 10 -> 3 -> 1 -> null
console.log(ll.removeAt(2)); // 3
ll.printNode(); // 2 -> 10 -> 1 -> null

console.log(ll.size()); // 3

이중 연결 리스트

각 노드가 데이터와 포인터를 가지며, “두 줄"로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

function Node(data) {
  this.data = data;
  this.next = null;
  this.prev = null;
}

function DoubleLinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}

DoubleLinkedList.prototype.size = function () {
  return this.length;
};
DoubleLinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};
DoubleLinkedList.prototype.printNode = function () {
  let print = "";
  print += `head -> `;
  for (let node = this.head; node != null; node = node.next) {
    print += `${node.data} -> `;
  }
  print += "null";

  console.log(print);
};
DoubleLinkedList.prototype.printNodeInverse = function () {
  let temp = [];
  let print = "";

  print += `null <- `;
  for (let node = this.tail; node != null; node = node.prev) {
    temp.push(node.data);
  }
  for (let i = temp.length - 1; i >= 0; i--) {
    print += `${temp[i]} <- `;
  }
  print += "tail";
  console.log(print);
};
DoubleLinkedList.prototype.append = function (data) {
  let newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }
  this.length++;
};
DoubleLinkedList.prototype.insert = function (data, position = 0) {
  if (position < 0 || position > this.length) {
    return false;
  }

  let newNode = new Node(data),
    current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = current;
      current.prev = newNode;
      this.head = newNode;
    }
  } else if (position === this.length) {
    current = this.tail;
    current.next = newNode;
    newNode.prev = current;
    this.tail = newNode;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    newNode.next = current;
    prev.next = newNode;

    current.prev = newNode;
    newNode.prev = prev;
  }

  this.length++;

  return true;
};
DoubleLinkedList.prototype.remove = function (data) {
  let current = this.head,
    prev = current;

  while (current.data != data && current.next != null) {
    prev = current;
    current = current.next;
  }

  if (current.data != data) {
    return null;
  }

  if (current === this.head) {
    this.head = current.next;

    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (current === this.tail) {
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    prev.next = current.next;
    current.next.prev = prev;
  }

  this.length--;

  return current.data;
};
DoubleLinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    return null;
  }

  let current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    this.head = current.next;
    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (position === this.length - 1) {
    current = this.tail;
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    prev.next = current.next;
    current.next.prev = prev;
  }

  this.length--;

  return current.data;
};
DoubleLinkedList.prototype.indexOf = function (data) {
  let current = this.head,
    index = 0;

  while (current != null) {
    if (current.data === data) {
      return index;
    }

    index++;
    current = current.next;
  }

  return -1;
};

const dll = new DoubleLinkedList();

dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2, 1);
dll.insert(3, 3);
dll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null
dll.printNodeInverse(); // null <- 100 <- 2 <- 10 <- 3 <- 1 <- tail

console.log(dll.indexOf(1000)); // -1 (없으면 -1 반환)
console.log(dll.indexOf(1)); // 4
console.log(dll.indexOf(100)); // 0
console.log(dll.indexOf(10)); // 2

console.log(dll.remove(100)); // 100
dll.printNode(); // 2 -> 10 -> 3 -> 1 -> null
console.log(dll.removeAt(2)); // 3
dll.printNode(); // 2 -> 10 -> 1 -> null

console.log(dll.size()); // 3

원형 연결 리스트

각 노드가 데이터와 포인터를 가지며, “원형 형태”로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

function Node(data) {
  this.data = data;
  this.next = null;
}
function CircularLinkedList() {
  this.head = null;
  this.length = 0;
}

CircularLinkedList.prototype.size = function () {
  return this.length;
};
CircularLinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};
CircularLinkedList.prototype.printNode = function () {
  let print = "";
  print += "head -> ";

  if (this.length != 0) {
    print += `${this.head.data} -> `;
    for (let node = this.head.next; node != this.head; node = node.next) {
      print += `${node.data} -> `;
    }
  }
  print += `null`;
  console.log(print);
};
CircularLinkedList.prototype.append = function (data) {
  let newNode = new Node(data),
    current = this.head;

  if (this.head === null) {
    this.head = newNode;
  } else {
    while (current.next != this.head) {
      current = current.next;
    }
    current.next = newNode;
  }

  newNode.next = this.head;

  this.length++;
};
CircularLinkedList.prototype.insert = function (data, position = 0) {
  if (position < 0 || position > this.length) {
    return false;
  }

  let newNode = new Node(data),
    current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    newNode.next = current;

    if (this.isEmpty()) {
      current = newNode;
    } else {
      while (current.next != this.head) {
        current = current.next;
      }
    }

    this.head = newNode;
    current.next = this.head;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    newNode.next = current;
    prev.next = newNode;

    if (newNode.next === null) {
      newNode.next = this.head;
    }
  }

  this.length++;

  return true;
};
CircularLinkedList.prototype.remove = function (data) {
  let current = this.head,
    prev = current,
    value;

  while (current.data != data && current.next != this.head) {
    prev = current;
    current = current.next;
  }

  if (current.data != data) {
    return null;
  }

  value = current.data;

  if (current === this.head) {
    while (current.next != this.head) {
      current = current.next;
    }
    this.head = this.head.next;
    current.next = this.head;
  } else {
    prev.next = current.next;
  }

  this.length--;

  return value;
};
CircularLinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    return null;
  }

  let current = this.head,
    index = 0,
    prev,
    value;

  if (position === 0) {
    value = current.data;

    while (current.next != this.head) {
      current = current.next;
    }
    this.head = this.head.next;
    current.next = this.head;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    value = current.data;
    prev.next = current.next;
  }

  this.length--;
  return value;
};
CircularLinkedList.prototype.indexOf = function (data) {
  let current = this.head,
    index = 0;

  do {
    if (current.data === data) {
      return index;
    }
    index++;
    current = current.next;
  } while (current != this.head);

  return -1;
};

const cll = new CircularLinkedList();

cll.insert(1);
cll.insert(10);
cll.insert(100);
cll.insert(2, 1);
cll.insert(3, 3);
cll.printNode(); // head -> 100 -> 2 -> 10 -> 3 -> 1 -> null

console.log(cll.indexOf(1000)); // -1 (없으면 -1 반환)
console.log(cll.indexOf(1)); // 4
console.log(cll.indexOf(100)); // 0
console.log(cll.indexOf(10)); // 2

console.log(cll.remove(100)); // 100
cll.printNode(); // head -> 2 -> 10 -> 3 -> 1 -> null
console.log(cll.removeAt(2)); // 3
cll.printNode(); // head -> 2 -> 10 -> 1 -> null

console.log(cll.size()); // 3

stack

LIFO(Last In First Out) 기반의 선형 자료 구조

function Stack(array) {
  this.array = array ? array : [];
}
Stack.prototype.getBuffer = function () {
  return this.array.slice();
};
Stack.prototype.isEmpty = function () {
  return this.array.length === 0;
};
Stack.prototype.push = function (element) {
  return this.array.push(element);
};
Stack.prototype.pop = function () {
  return this.array.pop();
};
Stack.prototype.peek = function () {
  return this.array[this.array.length - 1];
};
Stack.prototype.size = function () {
  return this.array.length;
};
// position 0 ~ this.array.length - 1까지 범위 안에 element가 있는지
Stack.prototype.indexOf = function (element, position = 0) {
  for (let i = position; i < this.array.length; i++) {
    if (element === this.array[i]) return i;
  }
  return -1;
};

Stack.prototype.includes = function (element, position = 0) {
  for (let i = position; i < this.array.length; i++) {
    if (element === this.array[i]) return true;
  }
  return false;
};

let stack = new Stack([1, 2, 3]);

queue

non-linear data structure