[CS 기초] Linked List

또다시 CS 기초를 공부한다. 기초를 공부하자고 마음을 먹을 때마다 Linked list로 공부를 시작하게 된다. 그만큼 기본적이라는 거겠지?

 

Linear Data Structure & Non Linear Data Structure

Linked List 를 공부할 때 알아두어야 할 용어가 있다. LDS, NLDS.

LDS는 리스트를 아이템에 접근(traverse) 하거나 생성할 때 순서가 중요시되는 데이터 구조를 말한다.

대표적인 LDS 중 Array List 나 Linked List 는 모든 node/item을 거쳐야 리스트에 끝으로 진입할 수 있다는 것이다.

- Sequence & has an order

 

그림으로 그리면 이런 느낌일까 ..

대표적인 NLDS는 dictionary, graph, tree 등이 있다.

 

Static Data Structure & Dynamic Data Structure

Array List와 Linked List는 메모리를 어떻게 할당/관리하는 것에 차이가 있다.

 

a = [1,2,3,4,5,6]

 

a라는 변수 안에 배열을 할당했을 때 array list는 메모리 상에서 연결된/인접한 6개의 메모리 블록이 있어야 한다는 것이다.

하지만 Linked List는 Dynamic Data Structure 이기 때문에 메모리가 연결되어있지 않아도 어디에든 저장할 수 있다.

그럼 Linked List는 왜 위에처럼 메모리를 사용할 수 있는 걸까..?

 

 

 

 

Linked List 를 구성하는 것을 아이템 또는 node 라고 부른다.

Linked list 첫번째 아이템은 head 라고 부른다. head 가 null 이라면 linked list 는 비었다는것이다.

노드는 데이터와 next 값을 갖고 있다. 데이터는 말 그래로 저장할 값을 얘기하고 next 는 다음 데이터의 주소값을 가지고 있다. node 하나가 다음 데이터의 주소값을 저장하고 있기 때문에 연속적으로 붙어있는 메모리가 필요하지 않고 필요에 따라 메모리 slot 을 삭제 할 수 도, 추가 할 수도 있다. Linked List 의 마지막 값을 알고 싶다면 처음 head 에서부터 next -> next -> 이렇게 따라가서 마지막 값을 찾아야한다.

 

 

Doubly Linked List는 전 노드의 정보를 갖고 있는 Linked List를 말한다. 위에 이미지에서 보여지는것 같이 head는 Linked List의 첫번째 아이템이기 때문에 데이터값과 다음(next) 정보만 갖고 있다. 그 다음 노드들은 PREV 라는 전 노드 주소값을 갖고 있어서 전 데이터 정보를 알 수 있다. Linked List 는 전 데이터 정보를 알 수 없다.