목차
오늘은 자료구조인 연결 리스트에 관해 공부를 해보려 합니다.
연결 리스트(Linked List)
이름에서 알 수 있듯이 Linked List는 링크를 이용해서 리스트를 만든다는 뜻입니다.
그림으로 간단히 나타내면 이런 형태입니다.
연결 리스트는 여러개의 노드로 이루어져 있고 각각의 노드는 데이터와 주소를 기억하고 있습니다.
연결 리스트 구조에서 맨 앞을 HEAD라고 하며 맨 마지막을 TAIL이라 합니다.
노드는 link를 통해 다음 노드에 접근할 수 있으며, 노드들은 다음에 올 노드의 정보를 가지고 있습니다.
(이해를 위해서 link라는 단어를 썼지만 link를 reference 혹은 address라고 합니다.)
자바스크립트를 알고 있는 저에게는 이거 배열이랑 비슷한거 아닌가? 생각이 들었습니다.
하지만 중요한 차이점이 있습니다.
자바스크립트 배열의 경우에는 임의 접근(Random Access)가 가능하지만 연결 리스트는 임의 접근이 불가능하고 순차적 접근을 하는 것이 차이점입니다. 임의 접근은 무엇일까요?? 순차적 접근은 무엇일까요?? 아래에서 천천히 설명하겠습니다.
연결 리스트의 데이터 접근과 시간 복잡도
연결 리스트는 순차적 접근을 한다고 말씀드렸습니다. 순차적 접근이라고 하면 글에서도 알 수 있듯이 순서대로 접근을 하는 것입니다.
이 구조에서 맨 앞을 Head라고 부릅니다.
그렇기에 어떤 특정 데이터를 찾으려면 Head에서 시작하여 다음 노드들에 접근을 하는 방식으로 찾습니다.
데이터가 1,2,3을 가지고 있는 노드가 있다고 가정하겠습니다. 제가 찾고 싶은 데이터는 3입니다.
위의 그림에서 보이듯이 head에서 출발하여 다음 노드로 이동하여 데이터를 비교한 후 데이터가 3일 때까지 다음 노드로 이동을 해야합니다. 시간 복잡도는 O(n)이 될 것입니다. 그러면 랜덤 엑세스가 가능한 배열의 경우에는 어떨까요??
배열의 데이터 접근과 시간 복잡도
배열에서 특정 데이터를 찾아내려면 당연히 시간 복잡도는 O(n)일 것입니다. find 메서드를 이용해서 찾는다고 생각하시면 이해하기 쉬울 것입니다. 하지만 랜덤 엑세스의 관점에서 보면 시간 복잡도는 O(1)입니다. 아래 코드를 볼까요?
const arr = [1,2,3];
// find Method 이용한 접근 (시간복잡도: O(n) )
console.log(arr.find((item) => item === 3));
// Random Access 이용한 접근 (시간복잡도: O(1) )
console.log(arr[2]);연결 리스트와 배열의 차이점이 많지만 저는 위의 설명드린 차이점이 중요하다고 생각합니다.
그러면 이제 연결리스트를 자바스크립트에서 구현해보겠습니다.
연결 리스트(Linked List) 구현 (간단하게)
class ListNode {
constructor(value) {
this.value = value;
this.next = null;
}
}
function getNodeArray(node) { // 노드들의 값을 배열의 형태로 반환하는 함수
const array = [];
let currentNode = node;
while(currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.next;
}
return array;
}
const headNode = new ListNode(1); // head 노드를 생성 (데이터 1)
headNode.next = new ListNode(2); // head노드가 가리키는 next 노드를 생성 (데이터 2)
headNode.next.next = new ListNode(3); // head노드가 가리키는 next 노드의 next 노드를 생성 (데이터 3)
headNode.next.next.next = new ListNode(4); // head노드가 가리키는 next 노드의 next 노드의 next노드를 생성 (데이터 4)
headNode.next.next.next = null; // 마지막 노드 삭제위의 코드처럼 처음에 head노드에 해당하는 객체를 생성하고 생성할 때는 value를 받아서 객체에 값을 저장하고 next는 null로 선언합니다. 개념에서 설명하였던 데이터는 여기에서 value이고 Link는 next라는 이름으로 선언되어 있습니다.
이렇게하면 직관적으로 노드들이 연결되는 것을 볼 수 있을 것 같습니다. (저만 그런가요..)
연결 리스트 구현 (조금 복잡하게)
위에서 보인 구현방식은 생성할 때마다 next.next.next.next.next .... 이렇게 해야해서 나중에 코드를 해석하기 어려울 것 같습니다.
이번에는 메서드로 각 노드들을 추가하고 삭제하고 중간에 삽입하는 그런 코드를 구현해보겠습니다.
위에 코드는 ES6에 나온 Class문법을 썼으니 이번에는 기존의 ES6 이전 버전에서 사용 가능한 문법으로 작성해볼게요.(이게 이해가 더 잘되실 것 같아서요. 요청해주시면 class문법으로 바꾸겠습니다.)
function Node(value) {
this.value = value;
this.next = null;
}
function LinkedList() {
// field
this.head = new Node('head');
// method
this.append = function(value) { // 배열에서 push하는 것이랑 유사합니다.
var newNode = new Node(value);
var currentNode = this.head;
while(currentNode.next !== null) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
this.find = function(item) {
var currentNode = this.head;
while(currentNode.value !== item) {
currentNode = currentNode.next;
}
return currentNode;
}
this.findPrevious = function(item) {
var currentNode = this.head;
while(currentNode.next !== null && currentNode.next.value !== item) {
currentNode = currentNode.next;
}
return currentNode;
}
this.insert = function (value, item) {
var insertNode = new Node(value);
var currentNode = this.find(item); // 현재 노드 찾기
insertNode.next = currentNode.next; // 삽입할 노드의 next를 찾아낸 노드의 next로 변경
currentNode.next = insertNode; // 현재 노드가 가리키고 있는 next를 삽입할 노드로 변경
}
this.remove = function (item) {
var currentNode = this.findPrevious(item); // 해당하는 노드의 전(prev) 노드를 찾기
currentNode.next = currentNode.next.next; // 찾은 노드의 next를 다다음 노드로 연결 기존 노드와의 연결이 끊겨짐
}
this.getValueArray = function() { // LinkedList를 받아서 연결 리스트의 값들을 배열로 리턴
var array = [];
var currentNode = this.head;
while(currentNode !== null) {
array.push(currentNode.value);
currentNode = currentNode.next;
}
return array;
}
}
var linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.insert(10, 1);
linkedList.remove(2);
console.log(linkedList.getValueArray()); // ['head', 1, 10]
부족한 글 읽어주셔서 감사합니다.
