[알고리즘] 연결 리스트(LinkedList)와 구현 메서드

TDL에 정리하기에는 너무 내용이 길어서, 보기 쉽게 한 번에 정리하기 위하여 TIL로 작성.
Linked-list를 1부터 6까지 다양한 구현 메서드를 활용해보자!

---

• 연결 리스트 (Linked List)
  • 각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
  • 구현 메서드(method)
    • 노드 개수/ 비어 있는지 확인/ 노드 출력 : LinkedList.size(), LinkedList.isEmpty(), LinkedList,printNode()
    • 노드 추가 : LinkedList.append(), LinkedList.insert()
    • 노드 삭제 : LinkedList.remove(), LinkedList.removeAt()
    • 데이터 위치 확인 : LinkedList.indexOf()

---

• LinkedList-1
  1. Node : data와 point를 가지고 있는 객체
  2. LinkedList : head와 length를 가지고 있는 객체
  3. size : LinkedList 내 노드 개수 확인
  4. isEmpty : LinkedList 내 노드 존재 여부 파악

// Node() : data와 point를 가지고 있는 객체
function Node(data) {
	this.data = data;
	this.next = null;
}

// LinkedList() : head와 length를 가지고 있는 객체
function LinkedList() {
	this.head = null;
	this.length = 0;
}

// size() : 연결 리스트 내 노드 개수 확인
LinkedList.prototype.size = function () {
	return this.length;
};

// isEmpty() : 객체 내 노드 존재 여부 파악
LinkedList.prototype.isEmpty = function () {
	return this.length === 0;
};

let ll = new LinkedList();
ll.head = new Node(123);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: null }, length: 1 }

ll.head.next = new Node(456);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: Node { data: 456, next: null } }, length: 2}

---

• LinkedList-2
  1. printNode() : LinkedList를 반복문을 통해 탐색하면서 갖고 있는 노드를 출력하고, 마지막(next)에 null을 출력.
  LinkedList의 상태를 가시적으로 보여주는 메서드.
  2. append() : LinkedList 가장 끝에 노드 추가.
  append 메서드가 없다면? 위 LinkedList-1처럼 계속해서 일일이 노드를 붙여줘야 한다.

 

• append 메서드 없이 printNode를 실행했을 경우.

// printNode() : 노드 출력
LinkedList.prototype.printNode = function () {
	for (let node = this.head; node != null; node = node.next) {
		process.stdout.write(`${node.data} -> `);
	}
	console.log("null");
};

let ll = new LinkedList();

ll.head = new Node(123);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: null }, length: 1 }

ll.head.next = new Node(456);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: Node { data: 456, next: null } }, length: 2 }

ll.head.next.next = new Node(789);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: Node { data: 456, next: [Node] } }, length: 3 }

ll.head.next.next.next = new Node(999);
ll.length++;
console.log(ll); // LinkedList { head: Node { data: 123, next: Node { data: 456, next: [Node] } }, length: 4 }

ll.printNode(); // 123 -> 456 -> 789 -> 999 -> null

 

• append를 사용하여 LinkedList를 구현할 경우

// append() : 연결 리스트 가장 끝에 노드 추가
LinkedList.prototype.append = function (value) {
  let node = new Node(value),
    current = this.head;

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

let ll = new LinkedList();

ll.append(1);
ll.append(5);

ll.printNode(); // 1 -> 5 -> null
console.log(ll.size()); // 2

1. value값 1을 인자로 받아서 node에 할당해주고, this.head는 current로 할당.
2. 현재 this.head가 null인 상태니까, 조건문이 true로 되며 this.head에 node를 할당하고 length를 하나 늘려줌.
   그러므로, 현재 head에는 하나의 node (data: 1, next: null)가 들어있음.
   ll.append(1) 식은 여기까지. 만약 printNode를 한다면 1 -> null, size는 1
3. value값 5를 인자로 받아서 node에 할당. 현재 this.head에는 하나의 node (data: 1, next:null)가 있기에 null이 아님
4. 따라서 if를 제치고 else로 가서 현재 current.next는 node (data: 1)인데, null이 아니기에 while문을 돌면서
   current(head)를 current.next(node (data: 1, next: null))로 업데이트해준다.
5. 그 후 다시 while문 처음으로 가서 현재 current.next는 node(data:1, next:null)이므로,
   반복문을 빠져나오고 current.next(null)에 node(data: 5, next:null)를 할당해주고, length에 1 추가.
6. ll.append(5) 식은 여기까지. 두 개의 node (data: 1, node (data: 5, next: null))가 들어있으며
   만약 printNode를 한다면 1 -> 5 -> null, size는 2

---

• LinkedList-3
• insert() : position 위치에 노드 추가 (앞쪽으로 추가됨)

// insert() : position 위치에 노드 추가 (앞쪽으로)
LinkedList.prototype.insert = function (value, position = 0) {
  if (position < 0 || position > this.length) {
    return false;
  }

  let node = new Node(value),
      current = this.head,
      index = 0,
      prev;

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

  return true;
};

let ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.printNode(); // 10 -> 1 -> null

ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 10 -> 2 -> 1 -> 3 -> null

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

• position이 default일 경우
  1. ll.insert(1) : position이 0이므로, 두 번째 조건문에 부합한다.
     node.next는 current인데, current는 this.head니까 현재 head는 null이므로, 따라서 node.next는 null을 할당.
     그리고, this.head는 node (data: 1)을 할당.
     printNode를 할 경우 : 1 -> null
  2. ll.insert(10) : position은 역시 0.
     node.next는 current인데, current는 this.head니까 현재 head는 (data: 1)이므로, node.next는 1을 할당.
     그리고, this.head는 node (data: 10)을 할당해주자.
     결론적으로, head는 10 -> node.next는 1 -> node.next.next는 null
     printNode를 할 경우 : 10 -> 1 -> null
• position을 인자로 받아왔을 경우
  1. ll.insert(2, 1) : 두 번째 조건문에서 position이 0이 아니므로, else에 부합한다.
     현재 index는 0이고 position은 1이므로, 0 < 1로 true. 반복문을 돈다.
     prev는 current고, 위에서 current는 this.head니까 head를 가리키고 있는 10을 할당.
     current는 current.next를 할당해주어야 하니깐, 10 다음 노드의 1을 할당.
     node.next는 current를 할당해주어야 하니깐, 1을 할당.
     prev.next는 node를 할당해주어야 하니깐 value 2를 넣고 추가한 노드 2를 할당.
     결론적으로, prev는 10 -> prev.next, current는 2 -> node.next는 1 -> null
     printNode를 할 경우 : 10 -> 2 -> 1 -> null

---

• LinkedList-4
• remove() : value 데이터를 찾아 노드 삭제
  value값을 받아서 node 내의 data와 value가 동일한지 판단을 한 후에 같다면 제거, 같지 않다면 null.

// remove() : value 데이터를 찾아 노드 삭제
LinkedList.prototype.remove = function (value) {
  let current = this.head,
      prev = current;

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

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

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

  return current.data;
};

let ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 10 -> 2 -> 1 -> 3 -> null

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

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

• II.remove(1000)
  1. ll.remove(1000) : 현재 this.head는 10이므로 current에 10을 할당해주고, prev 또한 10.
  2. 반복문 :
     current.data가 10이므로 value인 1000과 같지 않고, current.next는 2로 null이 아님 => prev는 10, current는 2
     current.data가 2이기에 value인 1000과 같지 않고, current.next는 1로 null이 아님 => prev는 2, current는 1
     current.data가 1,  value인 1000과 같지 않고, current.next는 3으로 null이 아님 => prev는 1, current는 3
     current.data가 3이기에 value인 1000과는 같지 않고, current.next는 null로 반복문을 빠져나온다.
  3. 만약 current.data(3)가 value(1000)와 같지 않을 때는 null을 리턴해주므로, null을 바로 리턴
• ll.remove(1)
  1. 현재 this.head는 10이므로 current에 10을 할당해주고, prev 또한 10.
  2. 반복문 :
     current.data가 10이므로 value인 1과 같지 않고, current.next는 2로 null이 아님 => prev는 10, current는 2
     current.data가 2이기에 value인 1과 같지 않고, current.next는 1로 null이 아님 => prev는 2, current는 1
     current.data가 1이기에 value인 1과 같아서 반복문을 빠져나온다.
  3. current(1)가 this.head(10)가 아니기에 prev.next에 current.next(3)를 할당.
  4. length를 1 빼 주고, current.data(1)를 리턴해준다.
     그렇게 된다면 return값은 1이며,
     printNode를 할 경우 10 -> 2 -> 3 -> null
• ll.remove(3)
  1. 현재 this.head는 10이므로 current에 10을 할당해주고, prev 또한 10.
  2. 반복문 :
     current.data가 10이므로 value인 3과 같지 않고, current.next는 2로 null이 아님 => prev는 10, current는 2
     current.data가 2이기에 value인 3과 같지 않고, current.next는 1로 null이 아님 => prev는 2, current는 1
     current.data가 1이기에 value인 3과 같지 않고, current.next는 1로 null이 아님 => prev는 1, current는 3
     current.data가 3이기에 반복문을 빠져나온다.
  3. current(3)가 this.head(10)가 아니기에 prev.next에 current.next(null)를 할당.
  4. length를 1 빼 주고, current.data(3)를 리턴해준다.
     그렇게 된다면 return값은 3이며,
     printNode를 할 경우 10 -> 2 -> nullll.remove(3)

---

• LinkedList-5
  • removeAt() : position 위치 노드 삭제

// removeAt() : position 위치 노드 삭제
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;
};

let ll = new LinkedList();

ll.insert(1);
ll.printNode(); // 1 -> null
ll.insert(10);
ll.printNode(); // 10 -> 1 -> null

ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 10 -> 2 -> 1 -> 3 -> null

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

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

• ll.removeAt(1000)
  1. position이 this.length보다 크므로, null
• ll.removeAt(1)
  1. current는 10이며, index는 0.
  2. position이 1이므로, else문으로 넘어간다.
  3. index는 0이므로 1인 position보다 작은 게 맞으므로 반복문을 돌린다.
     prev는 current를 할당, 즉 this.head인 10을 할당하고,
     current는 다시 current.next 즉 2를 할당하며 반복문을 끝낸다.
  4. prev.next(2)에 1인 current.next이 넣어지면서 10과 1 사이에 있던 node2가 자동으로 삭제됨.
     즉, 10 -> 1 -> 3 -> null 이 되며, current.data는 2
• ll.removeAt(0)
  1. current는 10이며, index는 0
  2. position이 0이므로, if문안으로 동작.
  3. this.head는 current.next인 1을 할당받는다.
  4. prev.next는 current.next인 1을 할당받는다.
  5. 즉 1 -> 3 -> null 이 되며, current.data는 10

---

• LinkedList-6
  • indexOf() : value 값을 갖는 노드 위치 변환

// indexOf() : value 값을 갖는 노드 위치 반환
LinkedList.prototype.indexOf = function (value) {
	let current = this.head,
		index = 0;

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

		index++;
		current = current.next;
	}

	return -1;
};

// remove2() : indexOf + removeAt = remove
LinkedList.prototype.remove2 = function (value) {
	let index = this.indexOf(value);
	return this.removeAt(index);
};

let ll = new LinkedList();

ll.insert(1);
ll.printNode(); // 1 -> null
ll.insert(10);
ll.printNode(); // 10 -> 1 -> null

ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 10 -> 2 -> 1 -> 3 -> null

console.log(ll.indexOf(1000)); // -1
console.log(ll.indexOf(1)); // 2
console.log(ll.indexOf(10)); // 0

console.log(ll.remove2(1000)); // null
ll.printNode(); // 10 -> 2 -> 1 -> 3 -> null
console.log(ll.remove2(1)); // 1
ll.printNode(); // 10 -> 2 -> 3 -> null
console.log(ll.remove2(10)); // 10
ll.printNode(); // 2 -> 3 -> null

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

• ll.indexOf(1000)
  1. value는 1000, current는 10, index는 0
  2. current는 null이 아니므로, 반복문을 돌린다.
     if문에는 해당이 안 되므로, index+1로 1, current는 current.next로 2가 된다.
     index+1로 2, current는 current.next로 1
     index+1로 3, current는 current.next로 3
     index+1로 4, current는 current.next로 null
     current는 null 이므로, return -1
• ll.indexOf(1)
  1. value는 1, current는 10, index는 0
  2. current는 null이 아니므로, 반복문을 돌린다.
     current.data에 value값 1과 같은 data와 같은 index 2를 리턴해준다.
• ll.indexOf(10)
  1. value는 10, current는 10, index는 0
  2. current는 null이 아니므로, 반복문을 돌린다.
     current.data에 value값 10과 같은 data와 같은 index 0를 리턴해준다.
• ll.remove2(1000)
  1. value값 1000의 indexOf의 리턴 값은 null 이므로, 이 메서드 또한 null을 리턴해준다.
• ll.remove2(1)
  1. value값의 indexOf의 리턴값은 2
  2. removeAt은 인덱스 위치 기준 노드를 삭제해주므로,
     인덱스 2인 1을 삭제하여, 1을 리턴하고
     printNode에는 10 -> 2 -> 3 -> null을 출력.
• ll.remove2(10)
  1. value값의 indexOf의 리턴값은 0
  2. removeAt은 인덱스 위치 기준 노드를 삭제해주므로,
     인덱스 0인 10을 삭제하여, 10을 리턴하고
     printNode에는 2 -> 3 -> null을 출력.

---

[ 출처, 참고 : 제로베이스 프런트엔드 스쿨 ]