🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
연결 리스트(Linked List)
📍 연결 리스트(Linked List)
👉🏻 저장하려는 데이터들을 분산해 할당하고 데이터들을 노드로 서로 연결해 줌
👉🏻 첫 노드의 주소를 알고 있으면, 연결되는 다음 데이터도 모두 알 수 있음
👉🏻 노드: 데이터를 담는 변수 하나와 다음 데이터를 가리키는 변수 1개를 가지고 있음
📍 장점
👉🏻 빈 메모리 공간 아무 곳에나 생성 후 연결만 해 주면 되기 때문에 초기 크기를 알지 않아도 됨
👉🏻 중간에 데이터를 삽입할 때도 다음 노드의 연결만 바꾸어 주면 되기 때문에 간편함 (삭제도 마찬가지)
📍 단점
👉🏻 데이터가 모두 떨어져 있어 바로 접근 불가능(4번째 노드에 접근하고 싶다면 첫 번째 노드를 기준으로 다음 데이터로 하나씩 넘어가야 함)
👉🏻 데이터 참조 O(n)의 성능을 가짐
📍 배열과 연결 리스트
👉🏻 배열의 크기는 고정 / 연결 리스트의 크기는 동적
👉🏻 배열의 주소는 연속 할당 / 연결 리스트의 주소는 불연속(런타임)
👉🏻 배열의 데이터 참조 성능 O(1) / 연결 리스트의 데이터 참조 성능 O(n)
👉🏻 배열의 삽입과 삭제 성능 O(n) / 연결 리스트의 삽입과 삭제 성능 O(n)
✔️ 참조를 자주 한다면 배열 사용, 삽입과 삭제가 자주 일어난다면 연결 리스트를 사용하는 것이 메모리 절약에 효율적!
🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
연결 리스트 구현
📍 추상 자료형(Abstract Data Type)
👉🏻 어떤 데이터와 그 데이터에 대한 연산 기능을 표기하는 것
👉🏻 연결 리스트의 추상 자료형
[ 테스트 코드 작성 ]
[ LinkedList.mjs ]
class Node{
// 클래스를 인스턴스화 했을 때 자동으로 호출되는 생성자 만들기
constructor(data, next = null){
// 생성자로 초기화
// next 기본값: null
// data는 필수지만 next는 입력하지 않을 경우 null 들어옴
// 클래스 내의 변수: 프로퍼티
this.data = data;
this.next = next;
}
}
// 다른 자바 스크립트 파일에서 node 클래스를 참조할 수 있게 export 줌
export { Node };[ test.mjs ]
// from 뒤에는 node 클래스가 저장된 파일의 경로를 적어 줌
import { Node } from './LinkedList.mjs';
// test.mjs에서 node 클래스를 사용할 수 있게 됨
// 테스트 코드 작성
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
// 연결 과정
node1.next = node2;
node2.next = node3;
console.log(node1.data);
console.log(node1.next.data);
console.log(node1.next.next.data);
[ 연결 리스트 클래스 만들기 ]
[ LinkedList.mjs ]
class LinkedList {
constructor(){
// 매개변수 필요 없음
this.head = null;
this.count = 0; // 총 노드 개수
}
// 함수의 원형
insertAt(index, data) {
if(index > this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
// 삽입할 노드 생성
let newNode = new Node(data);
if(index == 0) { // 새로 삽입하는 노드가 head임
newNode.next = this.head;
this.head = newNode;
} else { // 새로 삽입하는 노드가 head 아님
// 원하는 인덱스까지 노드 타고 들어가 새로 삽입
let currentNode = this.head;
// 목표 인덱스의 바로 전까지 접근
for(let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
newNode.next = currentNode.next;
currentNode.next = newNode;
}
this.count++;
}
}
export { Node, LinkedList };
1. 연결 리스트의 모든 데이터 출력 👉🏻 printAll()
printAll() {
let currentNode = this.head;
let text = "[";
while(currentNode != null) {
text += currentNode.data;
currentNode = currentNode.next;
if(currentNode != null) {
text += ", ";
}
}
text += "]";
console.log(text);
}[ test.mjs ]
list.printAll();
// 출력
2. 연결 리스트의 모든 데이터 제거 👉🏻 clear()
[ LinkedList.mjs ]
// 리스트 모든 함수 제거
clear() {
this.head = null;
this.count = 0;
}[ test.mjs ]
console.log("===== clear() 호출 =====");
list.clear(0);
list.printAll();
3. 인덱스 삽입 👉🏻 insertAt(index, data);
[ LinkedList.mjs ]
// 함수의 원형
insertAt(index, data) {
if(index > this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
// 삽입할 노드 생성
let newNode = new Node(data);
if(index == 0) { // 새로 삽입하는 노드가 head임
newNode.next = this.head;
this.head = newNode;
} else { // 새로 삽입하는 노드가 head 아님
// 원하는 인덱스까지 노드 타고 들어가 새로 삽입
let currentNode = this.head;
// 목표 인덱스의 바로 전까지 접근
for(let i = 0; i < index - 1; i++) {
currentNode = currentNode.next;
}
// 새로운 노드가 currentNode의 next를 가리킴
newNode.next = currentNode.next;
// currentNode가 새로운 노드를 가리킴
currentNode.next = newNode;
}
this.count++;
}[ test.mjs ]
console.log("===== insertAt() 다섯 번 호출 =====");
list.insertAt(0, 0);
list.insertAt(1, 1);
list.insertAt(2, 2);
list.insertAt(3, 3);
list.insertAt(4, 4);
// 삽입 완료
4. 마지막 데이터 뒤에 삽입 - 3번으로도 가능하나 조금 더 효율적으로 진행하기 위함 👉🏻 insertLast(data);
[ LinkedList.mjs ]
// 마지막 데이터 뒤에 삽입
insertLast(data){
this.insertAt(this.count, data);
}
[ test.mjs ]
console.log("===== insertLast() 세 번 호출 =====");
list.insertLast(0);
list.insertLast(1);
list.insertLast(2);
list.printAll();
5. 인덱스 삭제 👉🏻 deleteAt(index);
[ LinkedList.mjs ]
// deleteAt 함수 원형
deleteAt(index) {
if(index >= this.count || index < 0) {
throw new Error("제거할 수 없습니다.");
}
// 노드 순회 변수
let currentNode = this.head;
if(index == 0){ // 첫 번째 노드(head 노드) 제거
let deleteNode = this.head;
this.head = this.head.next;
this.count--;
return deleteNode;
} else { // 첫 번째 노드(head 노드)가 아닌 노드 제거
for(let i = 0; i < index - 1; i++){
currentNode = currentNode.next;
}
// 현재 currentNode는 제거할 노드의 이전 노드를 가리킴
let deleteNode = currentNode.next;
// 제거할 노드의 next 노드를 가리키게 함
currentNode.next = currentNode.next.next;
this.count--;
return deleteNode;
}
}
[ test.mjs ]
console.log("===== delteAt() 호출 =====");
list.deleteAt(0);
list.printAll();
list.deleteAt(1);
list.printAll();
6. 마지막 데이터 삭제 👉🏻 deleteLast();
[ LinkedList.mjs ]
deleteLast() {
return this.deleteAt(this.count - 1);
}
[ test.mjs ]
console.log("===== delteLast() 호출 =====");
// 현재 리스트에는 데이터 1개밖에 없으므로 하나 더 삽입
list.insertLast(5);
list.deleteLast();
list.deleteLast();
// 데이터 두 개인데 세 번 호출해서 "제거할 수 없습니다" 오류 남
// list.deleteLast();
list.printAll();
7. 원하는 인덱스의 데이터 읽기 👉🏻 getNodeAt(index);
[ LinkedList.mjs ]
getNodeAt(index) {
if(index >= this.count || index < 0) {
throw new Error("범위를 넘어갔습니다.");
}
// 리스트 순회 변수 만들어 헤드와 같은 노드 가리킴
let currentNode = this.head;
for(let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}[ test.mjs ]
console.log("===== getNodeAt() 호출 =====");
list.insertLast(1);
list.insertLast(2);
list.insertLast(3);
list.insertLast(4);
list.insertLast(5);
let secondNode = list.getNodeAt(2);
console.log(secondNode);