연결 리스트란?
- 각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
- 구현 메서드(method)
- 노드 개수/ 비어있는지 확인/ 노드 출력: LinkedList.size(), LinkedList.isEmpty(), LinkedList.printNode()
- 노드 추가: LinkedList.append(), LinkedList.insert()
- 노드 삭제: LinkedList.remove(), LinkedList.removeAt()
- 데이터 위치 확인: LinkedList.indexOf()
🔗 연결리스트 구현(1)
🔗 연결리스트 구현(2)
위의 결과에서 좀 더 가시적으로 나타내는 방법이 있다.
LinkedList를 반복문으로 탐색을 하면서 실제 데이터를 찍어주고, 마지막에 null값을 넣어줘서 LinkedList 내의 데이터들이 어떤식으로 값을 갖고있는지 화살표를 이용해 가시적으로 나타낼 수 있다.
위 코드를 넣어준 다음 text code 맨 아래에 ll.printNode() 를 넣어주고 실행하면 이렇게 값이 나온다.
➕ append() 활용
append() 메서드를 사용하면 연결 리스트 가장 끝에 노드가 자동으로 추가되도록 할 수 있다.
🔗 연결리스트 구현(3)
insert() 메서드를 사용하여 특정 position 위치에 노드를 추가할 수 있다.
ll.insert(2,1);: index 2번 자리에 1을 넣어라ll.insert(1)l: 1을 넣어라. (position이 없다. 노드 추가 메서드 부분 코드를 잘 보면function(value,position = 0)이 있는데, 위와 같이 position 이 따로 지정이 안됐을 경우 position = 0으로 진행하게 된다.
- head -> null 인 상태에서
ll.insert(1);을 해서 노드를 추가했다.- current는 현재 head를 가리키고 있다.
- if 문에서 position이 0일 경우, node.next는 current이고 윗부분에서 current는 this.head라고한다. this.head는 현재 null을 가리키기에 node.next는 head의 null을 가리키게된다.
- 그리고 this.head와 node를 연결한다.
- head -> 1 인 상태에서
ll.insert(10);노드를 추가했다.- if분을 보면, 다시 node.next는 current, 즉 this.head가 되고 this.head가 현재 가리키는 것은 노드의 1이기에 1을 가리키게 된다.
- 그리고 this.head는 새로운 노드의 10에 연결된다.
- head -> 10 인 상태에서
ll.insert(100);노드를 추가했다.- 똑같이 node.next는 current, 즉 this.head가 가리키는 10을 가리키게된다.
- this.head 는 node와 연결되면서 100을 가리키게된다.
그림을 그려보면 이러하다.
🔗 연결리스트 구현 (4)
remove() 메서드를 사용하여 value 데이터를 찾아서 해당 노드를 삭제할 수 있다.
코드의 결과가 100 -> 2 -> 10 -> 3 -> 1 -> null 이렇게 나온 상태에서 value값을 받은 remove 메서드인 (remove(value)) 를 실행시켜본다.
console.log(ll.remove(1000)); ll.printNode();-> value가 1000인 노드가 없으므로 return null
console.log(ll.remove(1)); ll.printNode();-> 1을 제거한 나머지 100 -> 2 -> 10 -> 3 -> null 이 출력된다.
console.log(ll.remove(100)); ll.printNode();-> 100을 제거하면 head가 업데이트 돼서 head -> 2 -> 10 -> 3 -> null 이 출력된다.
🔗 연결리스트 구현 (5)
removeAt() 메서드를 사용하여 특정 position 위치에 있는 노드를 삭제할 수 있다.
코드의 결과가 100 -> 2 -> 10 -> 3 -> 1 -> null 이렇게 나온 상태에서 노드의 position값 (index 번호)를 받아서 해당 노드를 삭제한다.
console.log(ll.removeAt(1000)); ll.printNode();-> position값이 1000인 노드가 없으므로 return null
console.log(ll.removeAt(4)); ll.printNode();-> position값이 4인 노드는 1이므로 1이 삭제된다.
console.log(ll.removeAt()); ll.printNode();-> position값으로 아무런 매개변수가 입력되지 않은 경우에는 초반에 position = 0 으로 설정해뒀기 때문에 0번인 100이 삭제된다.
🔗 연결리스트 구현 (6)
- indexOf() 메서드를 사용하여 value 값을 갖는 노드 위치를 반환할 수 있다.
- remove2() 메서드를 사용하여 value 값을 갖는 노드의 위치를 받아서 (indexOf(value)) 그 위치에 있는 노드를 삭제 (removeAt(index))한다.
코드의 결과가 100 -> 2 -> 10 -> 3 -> 1 -> null 이렇게 나온 상태에서 노드의 value 값을 받아서 해당 노드의 위치를 반환 한다.
console.log(ll.indexOf(1000)); ll.printNode();-> value값이 1000인 노드가 없으므로 return -1
console.log(ll.indexOf(1)); ll.printNode();-> value값이 1인 노드의 위치는 4
