[Linked Lists]1. 단일 연결 리스트 - 1

목차

1. ADT(Abstract data type)

2. Array vs Linked list

3. Singly Linked List

 

1. ADT란?

 ADT는 Abstract data type의 약자로서, 추상적인 자료형을 의미합니다. 이는 특정 자료형이

1. 어떤 데이터를 사용(저장)?

2. (저장하는 데이터로) 어떤 기능?

3. 성능 분석

 위 3가지를 분석하는 자료형을 뜻합니다. ADT의 종류에는 여러가지가 있으며, 우선 Array 와 Linked List에 대해서 알아보도록 하겠습니다.

 

2. Array vs Linked List?

 어떤 연속된 데이터를 저장한다고 하였을 시, 흔히 사용하는 방식으로 Array(배열)과 Linked List(연결 리스트)가 있습니다. 두 방법 모두 연속된 데이터를 저장하지만, 각각이 지니고 있는 장단점과 특징이 다릅니다.

 

1) Array(배열)

- 연속된 메모리 공간의 데이터를 사용함 (인접한 데이터들의 주소값은 실제로도 인접함)

- 배열의 크기 변화는 없움

- 제목이 곧 이름임

 

2) Linked List(연결 리스트)

- 동적이며, 추가적인 메모리 주소가 필요한 경우 그때그때 사용함

- 연속된 메모리 공간의 데이터가 아님 (인접한 데이터들의 주소값은 실제로 인접하지 않음)

 

3. Singly Linked List

 LInked List는 크게 Singly Linked List(단일 연결 리스트)와 Doubly Linked LIst(이중 연결 리스트) 2가지로 나뉘게 됩니다. 우선 Singly LInked List은 이름 그대로 단일(한 방향)으로 연결되어 있는 구조를 뜻합니다.

 

<Singly Linked List>

 위 그림과 같이 아래서 설명할 node가 일방향으로 연결되어 있으며, 그 마지막은 NULL값으로 이루어져 있습니다.

 

<node>

 각각의 자료형을 저장하는 node는 node 하나당 element(요소)와 다음 node의 주소값을 지니고 있습니다. 여기서 눈치챌 수 있는 사실은, node가 자신 다음의 node의 주소만 가지고 있다면 Singly Linked List, 이 뿐만 아니라 자신 이전의 node의 주소 또한 가지고 있다면 Doubly Linked List가 된다는 사실을 추측해 볼 수 있습니다.