-
연결리스트(Linked List)자료구조 2021. 12. 22. 02:31
특징
- 선형구조(하나의 자료 뒤에 하나의 자료만 존재한다, 데이터가 순차적으로 나열된 형태)
- 파편화된 메모리 공간 활용 가능
- 데이터와 다음 노드로의 연결 정보로 구성된 노드들의 집합으로 이루어진 자료구조
- 배열 크기가 제한되어 있지 않다.
- 단일, 이중, 원형 연결 리스트의 3가지 종류가 존재합니다.
장점
- 요소의 삽입과 제거가 효율적입니다. 요소들의 메모리 공간이 연속적이지 않기 때문에 삽입, 제거 후의 메모리 재배치가 필요하지 않기 때문입니다.
- 배열의 크기가 동적입니다.
단점
- index로 한 번에 요소에 접근하는 것이 불가능합니다. 첫 번째 노드부터 순차적으로 접근해야 합니다.
- 다음 노드로의 연결 정보 때문에, 배열보다 많은 메모리 공간을 필요로 합니다.
시간복잡도
단방향 연결리스트
- 조회(인덱스를 통한 접근), 탐색
- O(n) - n번째까지 모든 노드를 거쳐야 합니다.
- 삽입
- O(1) - 추가하려는 위치의 이전 노드를 알 경우
- O(n) - 추가하려는 위치의 이전 노드를 모를 경우, 이전 노드를 먼저 조회해야 합니다.
- 제거
- O(n) - 제거하려는 요소의 위치를 알아도 이전 노드의 포인터를 변경해줘야하기 때문에 조회가 필요합니다.
- 수정, 할당
- O(n) - 인덱스로 데이터를 관리하지 않기 때문에 일단 조회가 필요합니다.
양방향 연결리스트
- 조회(접근), 탐색, 수정, 할당
- O(n) - 인덱스로 데이터를 관리하지 않기 때문에 시간복잡도가 단방향 연결리스트와 동일합니다. 포인터의 갯수에 영향을 받지 않습니다.
- 삽입
- O(1) - 추가하려는 위치의 이전 노드를 알 경우
- O(n) - 추가하려는 위치의 이전 노드를 모를 경우, 이전 노드를 먼저 조회해야 합니다.
- 제거
- O(1) - 추가하려는 위치의 노드를 알 경우, 이전 노드를 가리키는 포인터가 있기 때문에 바로 그 노드에 접근하여 포인터를 수정할 수 있습니다.
사용처
- 가장 앞, 뒤의 삽입, 삭제에 유리한 특성 때문에 스택, 큐 구현에 사용됨
- 트리를 위한 발판
구현
단방향 연결리스트
class Node { constructor(data, next = null) { this.data = data; this.next = next; } } class LinkedList { constructor() { this.head = null; this.size = 0; } // 조회 getByIndex(index) { let currentNode = this.head; let count = 0; while (currentNode) { if (count == index) { return currentNode; } count++; currentNode = currentNode.next; } return null } // 탐색 search(data) { let currentNode = this.head; // 같은 데이터를 가진 노드까지 이동 while (currentNode.data !== data) { currentNode = currentNode.next; } return currentNode; } // 삽입 insert(data, index) { if (index == 0) { this.head = new Node(data, this.head); this.size += 1; return } if (index > this.size) { return } let newNode = new Node(data); // 삽입하고자 하는 인덱스 이전 노드를 찾는다 let previousNode = this.getByIndex(index - 1); // 이전 노드의 포인터를 복사하고 이전 노드의 포인터에 삽입할 노드를 연결한다 if (previousNode) { newNode.next = previousNode.next; previousNode.next = newNode; this.size += 1; } } // 삭제 removeByIndex(index) { // 삭제할 노드 이전 노드를 찾는다 let previousNode = this.getByIndex(index - 1); let removingNode = previousNode.next; // 삭제할 노드가 있다면, 이전 노드의 포인터에 삭제할 노드의 포인터를 할당 if (removingNode) { previousNode.next = removingNode.next; this.size -= 1; } else { // 없다면, null 할당 previousNode.next = removingNode; } } // 수정 updateByIndex(data, index) { // 수정할 노드를 찾는다. let targetNode = this.getByIndex(index); if (targetNode) { targetNode.data = data; } } printAll() { let currentNode = this.head; while (currentNode) { console.log(currentNode.data); currentNode = currentNode.next; } console.log(this.size); } } const sampleLinkedList = new LinkedList(); sampleLinkedList.insert("서울", 0); sampleLinkedList.insert("대전", 0); sampleLinkedList.insert("대구", 1); sampleLinkedList.insert("부산", 0); sampleLinkedList.removeByIndex(1); sampleLinkedList.updateByIndex("제주", 1); sampleLinkedList.printAll();<코드 실행 결과>
부산
제주
서울
3양방향 연결리스트
class Node { constructor(data, next = null, prev = null) { this.data = data; this.next = next; this.prev = prev; } } class LinkedList { constructor() { this.head = null; this.size = 0; } // 조회 getByIndex(index) { let currentNode = this.head; let count = 0; while (currentNode) { if (count == index) { return currentNode; } count++; currentNode = currentNode.next; } return null } // 탐색 search(data) { let currentNode = this.head; // 같은 데이터를 가진 노드까지 이동 while (currentNode.data !== data) { currentNode = currentNode.next; } return currentNode; } // 삽입 insert(data, index) { if (index == 0) { this.head = new Node(data, this.head); if (this.head.next) { this.head.next.prev = this.head; } this.size += 1; return } if (index > this.size) { return } let newNode = new Node(data); // 삽입하고자 하는 인덱스의 현재 노드를 찾는다 let currentNode = this.getByIndex(index); // 현재 노드가 있다면, 이전 앞을 가리키는 포인터와 이전 노드의 뒷 포인터를 카피하고 연결한다. if (currentNode) { let previousNode = currentNode.prev; newNode.next = currentNode; newNode.prev = previousNode; currentNode.prev = newNode; previousNode.next = newNode; this.size += 1; } } // 삭제 removeByIndex(index) { // 삭제할 인덱스의 노드를 찾는다 let currentNode = this.getByIndex(index); // 노드가 있으면, 이전 양쪽 포인터로 앞, 뒤 노드에 접근해 서로 연결 if (currentNode) { currentNode.prev.next = currentNode.next; currentNode.next.prev = currentNode.prev; this.size -= 1; } } // 수정 updateByIndex(data, index) { // 수정할 노드를 찾는다. let targetNode = this.getByIndex(index); if (targetNode) { targetNode.data = data; } } printAll() { let currentNode = this.head; while (currentNode) { console.log(currentNode.data); currentNode = currentNode.next; } console.log(this.size); } } const sampleLinkedList = new LinkedList(); sampleLinkedList.insert("서울", 0); sampleLinkedList.insert("대전", 0); sampleLinkedList.insert("대구", 1); sampleLinkedList.insert("부산", 0); sampleLinkedList.removeByIndex(1); sampleLinkedList.updateByIndex("제주", 1); sampleLinkedList.printAll();<코드 실행 결과>
부산
제주
서울
3참조