Linked List란? (+ 자료구조란?)

자료구조는 데이터의 표현 및 저장 방법을 의미한다. 아록리즘은 그 저장된 데이터를 처리하는 과정이다. 

즉, 자료구조를 알아야 알고리즘을 배울 수 있다. 특히 배열이 자료구조 중 하나이다. 자료구조에는 연결리스트, 스택, 큐 등이 있는데 자바스크립트의 배열은 이 모든 것을 표현할 수 있다. 

 

연결 리스트(linked-list)란?

링크 목록이란 뜻, 각 데이터들을 한 줄로 연결시킨 모양을 띄우고 있는 자료구조이다.

 

연결 리스트에서 데이터와 링크를 가지고 있는 박스를 (크기가 동적인 자료구조로 자료구조를 구성하는 요소)

노드라고 한다. 노드는 데이터만 가지고 있을 수도, 링크만 가지고 있을 수도 없다. 

무조건 노드는 데이터 + 링크를 가지고 있어야 한다. 위 사진에서와 같이 노드의 링크는 다음 데이터를 가리키고 있다.

링크를 통해 데이터를 추가하고, 삭제, 탐색이 가능하다. 

 

data1 부분이 헤드이고, 가장 마지막인 data4가 tail이고, link가 그 다음 data를 가르키는 부분이 pointer 역할을 하는 address 부분이다. tail의 pointer는 더 이상 가리킬 노드가 존재하지 않으므로 Null을 가르킨다. 

 

배열 리스트와 연결리스트의 장단점

배열리스트

가장 간단한 메모리 데이터 구조다

장점

- 동일한 데이터 타입을 연속적으로 저장할 수 있다.

- 간단하고, 사용이 쉬우며 데이터를 참조하기 쉽다.

단점

- 고정된 크기를 가지고 있어서 배열의 처음이나 중간에서 원소를 넣고, 빼려면 비싼 연산을 빈번하게 해야한다

 

연결리스트

일련의 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치 하지 않는다. 

노드로 구현된 리스트이기에 링크 하나에 4byte 메모리를 차지하며, 더블 링크 경우 노드 하나에 8byte를 차지

장점

- 배열에 비해 데이터의 추가 및 삽입이 용이하다

- 배열보다 메모리를 효율적으로 쓸 수 있다.

단점

- 특정 위치의 데이터를 검색하기 위해서는 처음부터 끝가지 순회해야 하기 때문에 탐색에 비효율적이다

 

Linked List의 작업별 시간복잡도

-prepend(맨 앞의 삽입) : O(1)

-append(맨 뒤의 삽입) : O(1)

-lookup(trabersal) : O(n)

-insert : O(n)

-delete : O(n)

 

포인터(Pointer)란?

const obj1 = { a: true};
const obj2 = obj1; // pointer

포인터는 기본적으로 원하는 데이터가 저장되어 있는 메모리 주소를 referencing 하는 작업이다. 위 코드의 경우 { a: ture} 라는 객체는 하나의 메모리 공간만 차지해서 저장되어 있다. 다만 obj1 과 obj2가 모두 그 메모리 주소를 참조하고 있을 뿐이다. 

참고로 자바스크립트에서는 포인터가 특정 메모리 주소를 참조하고 있을 경우, garbage collector가 해당 메모리 주소가 사용 중인 것으로 간주하여 메모리 공간에서 삭제되지 않는다.

 

const obj1 = { a: true};
const obj2 = obj1;
delete obj1;

console.log(obj1); //RefrenceError
console.log(obj2); // { a: true}

 

- 참조사이트

 

https://soldonii.tistory.com/

soldonii