[자료구조] 근본 자료구조인 연결리스트에 대해서

(00) :: Introduciton

대학교 학부 시절때 공부했던 이론 내용들을 리마인드 하기 위해서 작성된 게시글입니다.

정확하지 않은 내용이 포함되어 있는 경우, 댓글로 남겨주시면 수정할 수 있도록 하겠습니다.

이 게시글은 한 번에 완성되는 게시글이 아니며 내용을 지속적으로 추가할 예정입니다.

 

(01) :: Define a Concept

연결리스트 자료구조는 원소들을 저장할 때 다음 원소의 위치를 포함해서 저장하여 흩어져있는 원소들을 연결한 자료 구조입니다.

-----------     --------                    --------	 ---------
|   HEAD  | --> |  AA  | (Current Addr) --> |  BB  | --> |   CC  |
| POINTER | --> | 2,BB | (Data, Next)   --> | 4,CC | --> |77,NULL|
-----------     --------                    --------	 ---------

 

(02) :: Property

연결리스트는 한 원소에 데이터와 다음 원소를 가리키는 주소를 저장하는 구조 덕분에 다음과 같은 특성을 갖게 됩니다.

#1 O(K)로 K번째 원소를 확인하거나 변경할 수 있다.
#2 O(1)로 임의 위치에 원소를 추가하거나 임의 위치의 원소를 제거할 수 있다.
#3 배열과 달리 연속된 메모리 공간이 필요없어 비교적 할당이 쉽다. 그로 인해 캐시 적중률이 낮다.

 

또한 연결리스트는 원소의 구성과 원소 간 연결의 방식에 따라 종류를 구분할 수 있습니다.

#1 단일 연결 리스트(Singly Linked List)
- 헤드 포인터를 기점으로 한 원소의 원소의 데이터와 다음 원소를 가리키는 주소가 저장된다.
- 마지막 원소의 다음 원소를 가리키는 주소는 NULL 값이 저장된다.
-----------     --------                    --------	 ---------
|   HEAD  | --> |  AA  | (Current Addr) --> |  BB  | --> |   CC  |
| POINTER | --> | 2,BB | (Data, Next)   --> | 4,CC | --> |77,NULL|
-----------     --------                    --------	 ---------

#2 이중 연결 리스트(Doubly Linked List)
- 한 원소의 구성 요소가 이전 원소를 가리키는 주소도 추가된다.
-----------     --------                           ------------	     ------------
|   HEAD  | --> |  AA  | (Current Addr)       <--> |    BB    | <--> |    CC    |
| POINTER | --> | 2,BB | (Prev, Data, Next)   <--> |  AA,4,CC | <--> |BB,77,NULL|
-----------     --------                           ------------	     ------------

#3 원형 연결 리스트(Circular Linked List)
- 연결 리스트와 거의 동일하지만 마지막 원소의 Next가 첫 번째 원소의 주소를 가리킨다.
- 아래 예시는 단일 연결 리스트이지만, 이중 연결 리스트도 원형 연결 리스트가 될 수 있다.
-----------     --------                    --------	 ---------
|   HEAD  | --> |  AA  | (Current Addr) --> |  BB  | --> |   CC  | -----|
| POINTER | --> | 2,BB | (Data, Next)   --> | 4,CC | --> | 77,AA | -----|
-----------     --------                    --------	 ---------      |
                    ↑                                                   |
                    |                                                   |
                    ----------------------------------------------------|

 

 

(03) :: LinkedList, How it works?

배열과 연결리스트는 메모리 상에 원소를 놓는 방법이 다를뿐 원소 간 선후 관계가 1:1로 정의됩니다.

즉, 원소들 사이에서 N번째 원소의 개념이 존재한다는 뜻입니다.

그래서 배열과 연결리스트 자료구조를 '선형 자료구조'라고 칭합니다.

 

선형 자료구조인 배열과 연결리스트의 차이점을 이해하고 각 특징에 따라 적절하게 사용할 수 있어야 합니다.

예시) 임의 위치에 원소가 자주 추가/삭제 되는 경우 : 연결리스트 사용

예시) 원소가 자주 추가/삭제되지는 않는데 원소 자체에 접근이 많이 필요한 경우 : 배열 사용

#1. K번째 원소의 접근하는 경우 --> 배열 = O(1), 연결리스트 = O(K)
#2. 임의 위치에 원소를 추가하거나 제거하는 경우 --> 배열 = O(N), 연결리스트 = O(1)
#3. 메모리 주소 배치 방법은? --> 배열 = 연속, 연결 리스트 = 불연속
#4. 추가적으로 필요한 공간(메모리) 확보하는 경우 --> 배열 = 필요없음, 연결리스트 = O(N)

#1의 경우 배열은 인덱스를 통해 바로 접근하기 때문에 O(1)가 소요됩니다.

연결리스트는 다음 원소의 주소를 가리키고 있는 헤드 포인터를 시작으로 K번 접근해야 하므로 O(K)가 소요됩니다.

 

#2의 경우 배열은 기존에 존재하는 배열의 원소들을 뒤로 밀어야하기 때문에 O(N)이 소요됩니다.

연결리스트는 원소를 생성한 후 가리키는 주소만 바꿔주면 되기 때문에 O(1)이 소요됩니다.

 

#4의 경우 배열은 연속적인 메모리 공간을 확보해 놓기 때문에 데이터만 저장하면 돼서 추가적으로 필요한 공간이 없습니다.

연결리스트는 각 원소가 다음 원소 혹은 이전 원소의 주소를 가리킬 메모리 공간이 추가적으로 필요합니다.

32비트(4바이트) 컴퓨터면 4N 바이트가 추가로 필요하고, 64비트(8바이트) 컴퓨터면 8N 바이트가 추가로 필요합니다.

즉, N에 비례하는 메모리를 추가로 사용하게 됩니다.

 

(04) :: LinkedList, How to use in Java?

- 자바 API 활용한 사용 방법

- 실제 구현

 

(FF) :: Reference

참고자료는 다음과 같습니다.

# -- Thanks to --
#1 blog.encrypted.gg