자료구조 | 링크드리스트(Linked List) with JS

링크드리스트 (Linked List)

이후에 다루게 되는 트리, 그래프 같은 자료 구조의 밑바탕이 되는 자료구조이다. 

배열처럼 여러 개의 값을 순서대로 지정하기 위한 자료 구조이다. 

배열에서는 데이터가 정적 공간의 메모리에 순서대로 응집되어 저장된다면, 링크드 리스트는 데이터가 메모리에 흩어져서 저장된다. 

 

선형 데이터 구조는 삽입, 삭제 연산이 엄청나게 많을 경우, 원소들의 이동작업도 그에 따라 비례한다. 이는 성능상의 문제를 일으킬 수 있기 때문에 배열이 갖고있는 메모리 사용의 비효율성 문제를 그대로 갖고있다. 

 

특징

data의 입력과 삭제가 자유롭다. 새로운 데이터를 입력할 때, 세로운 데이터는 들어가고자하는  위치에 해당하는 앞 node의 tail에 자신의 data를 연결하고, 자신의 tail을 후위 node와 연결한다. 

 

1. 요소의 삽입 삭제시에 용이하다.

2. 특정 요소 검색에 비효율적이다.

 

그러나 Linked List에서는 중간에 삽입하더라도 바로 옆 공간에 넣을 필요가 없다. 아무데나 데이터를 넣은 다음 이전 요소가 새로운 요소를 가리키도록, 그리고 새로운 요소가 다음 요소를 가리키도록 링크의 연결만 조정해주면 쉽게 요소를 중간에 끼워넣을 수 있다. 그러므로 배열에서 요소를 중간에 삽입하는 것은 O(n)의 시간이 소요되고 Linked List에서는 O(1)이 소요된다.

 

 

링크드리스트 구현하려면?

자바스크립트에서 링크드리스트는 객체를 통해 구현할 수 있다. 

예시로 두 개의 객체를 next로 연결하여 링크드리스트의 기본 구조를 만들 수 있다. 

 

 

링크드리스트의 연산

링크드리스트에서 추가, 삭제, 삽입 연산을 하기 위해서는 탐색 과정이 필요하다. 출발 지점과 끝 지점이 있어야하고, head 변수를 만들고 이 변수를 기준으로 탐색을 한다. 

const linkedList =  () => {
	this.head = null; // 처음에 노드가 없으므로 null로 초기화
    this.length = 0; // 링크드리스트의 길이
}

링크드리스트에서 데이터의 삽입, 삭제는 2가지의 과정을 거친다.

 

1. 탐색

2. 연산

 

링크드리스트에 A → B → C 순서대로 데이터가 들어있고, 우리는 D라는 데이터를 B와 C 사이에 삽입하려고 한다. 

B와 D 가 필요하다. B를 가리키는 참조값(link)가 D가 들어있는 새 노드를 가리켜야하기 때문이다. 동시에 D가 다음으로 가리키는 참조값(link)를 C를 가리키게끔 해야한다. 

 

1) 데이터 추가

'head가 null 일 때 / head가 null이 아닐 때'를 나누어서 넣어준다. 

linkedList.add = (data) => {
	const newNode = new Node(data);
    if(this.head === null) {
    	this.head = newNode;
        this.length++;
    } else {
    	let currentNode = this.head;
        while(currentNode.link !== null) {
        	currentNode = currentNode.link;
        }
        currentNode.link = newNode;
        this.length++;
    }
}

1-1) 데이터 추가 (중간노드자리)

LinkedList.prototype.insertMiddleNode = (pre, data) => {
	const newNode = new Node(data);
    let currentNode = this.head;
    
    while(currentNode.data !== pre){
    	currentNode = currentNode.link;
    }
    
    let temp = currentNode.link;
    newNode.link = temp;
    currentNode.link = newNode;
    this.length++;
}

2-1) 데이터 제거 (마지막 노드)

LinkedList.prototype.remove = () => {
	let currentNode = this.head;
    while(currentNode.link.link !== null) {
    	currentNode = currentNode.link;
    }
    currentNode.link = null;
    thiks.length--;
}

2-2) 데이터 제거 (중간 노드)

if(currentNode.data !== data) {
	while(currentNode.link.data !== data) {
    	currentNode =  currentNode.link;
    }
    temp = currentNode.link.link;
    currentNode.link.link = null;
    currentNode.link = temp;
} else {
	temp = currentNode.link;
    currentNode.link = null;
    this.head = temp;
}
this.length--;

 

 

 

 

참고

1. https://velog.io/@raram2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A5%BC-%ED%86%B5%ED%95%9C-%EA%B5%AC%ED%98%84-Linked-List

2. https://taesung1993.tistory.com/10