Data Structure - linked list(Vol.1), (자료 구조-연결 리스트)

안녕하세요.

공상 개발입니다.

 

자료구조는 알고리즘과 더불어 컴퓨터공학부에서 중요하다고 자주 언급되는 과목인 만큼,

어느 정도 시간을 투자해야 됩니다.

이번 시간에는 자료구조 단원 중 하나인 연결 리스트(linked list)에 대해 간단히 알아보겠습니다.

---

2. 리스트(list)의 이해

2.1 배열을 이용한 리스트

 

3. 연결 리스트(linked list)의 이해

3.1 단순 연결 리스트(Singled Linked List)

3.2 원형 연결 리스트(Circular Linked List)

3.3 이중 연결 리스트(Doubled Linked List)

 

* 이번 linked list(Vol.1)에서는 굵게 표시된 개념들을 리뷰(review) 합니다.

---

 

2. 리스트(list)의 이해

 

 

리스트란?

리스트는  Stack, Queue, Tree 등과 같은 자료구조 구현에 활용될 기초 자료구조입니다.

선형적인 자료 형태를 보이는 자료구조를 리스트라고 말합니다.

---

 

2.1 배열을 이용한 리스트

 

리스트는 아래 두 가지의 방법에 따라서 구현할 수 있습니다.

 

 

우선 배열을 이용한 구현부터 살펴보겠습니다.

 

 

아마 자료구조를 배우는 컴퓨터공학 학부생이라면, 기본적으로 C언어에 대한 문법을 알고 있을 거라 생각합니다.

다양한 프로그램을 구현하면서 배열과 포인터에 대해 경험했을 것입니다.

배열을 이용한 구현은 우리가 이전에 경험한 것들과 크게 다르지 않습니다.

 

배열을 이용한 리스트 구현 코드

 

배열을 이용해 연결 리스트의 기능들을 구현한 코드입니다.

추상 자료형이 어색할 수 있으나,

 천천히 봐주시면 어렵지 않을 거라 생각합니다.

그림을 직접 그려서 이해해 보는 걸 추천합니다.

 

---

 

3. 연결 리스트(linked list)의 종류

 

다음으로 연결 리스트 종류들 중에

단순 연결 리스트에 대해 알아보겠습니다.

 

 

연결된 표현 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장 노드는 데이타 필드와 링크 필드로 구성  # 데이타 필드 - 리스트의 원소, 즉 데이타 값을 저장하는 곳  # 링크 필드 - 다른 노드의 주소값을 저장하는 장소 (포인터) 연결된 표현의 장단점 (vs. 배열을 이용한 리스트) 장점  # 삽입, 삭제가 보다 용이하다.  # 연속된 메모리 공간이 필요 없다. 단점  # 구현이 어렵다.  # i번째 데이터를 찾으려면 앞에서부터 순차적으로 접근하여야 한다.

 

즉, 연결 리스트는 배열이 가지고 있는 인덱스라는 장점 대신

빈틈없는

데이터 적재를 장점으로 취한 자료 구조라고 할 수 있습니다.

 

 

노드 구조

 

 

이번 시간에 다루는 단순 연결 리스트의 구조입니다.

 

 

---

 

3.1 단순 연결 리스트(Singled Linked List)

 

• 소스 코드

 

1

 

 

데이터 필드와 링크 필드로 구성된 노드를 구조체로 정의한 소스 코드입니다.

자기 참조 구조체를 사용한 걸 볼 수 있습니다.

이해를 돕기 위해,

자기 참조 구조체를 왜 사용했는지에 대해 예시를 들겠습니다.

 

1. a, b, c 노드가 존재한다.

3. a, b, c 노드는 연결 리스트 구조이다.

4. a 노드의 주소만 알고 있다면 b 노드와 c 노드에 접근할 수 있다.

5. 이를 가능하게 해 주는 게 자기 참조 구조체이다.

 

즉, 연결 리스트는 포인터와 구조체를 이용해 유동적으로 데이터를 저장할 수 있는 자료구조이며,

자기 참조 구조체를 연결해 사용합니다.

 

 

2

 

 

head 노드를 생성하고,

데이터 필드에 값을 넣어주고 주소 필드는 NULL을 가리킵니다.

 

 

3

 

 

 

p 노드를 생성하고,

데이터 필드에 값을 넣어주고 주소 필드는 NULL을 가리킵니다.

 

 

4

 

 

head가 가리키는 주소 필드에 p를 넣어주므로,

head는 p를 가리킵니다.

 

TIP : 여기서부터는 연산을 구현한 소스코드입니다.

포인터의 이해가 필요합니다.

 

위의 로직을 이해했다면, 여기서부터는 천천히 그림을 보며 직접 손으로 그려보시는 걸 추천합니다.

포인터와 관련된 내용은 장황하게 글로 설명된 글을 보는 것보다,

시각적인 이미지를 통해 본인이 직접 생각하는 게 이해에 있어 도움된다고 생각합니다. 

 

5

 

 

 

아래의 3가지 소스 코드는 직접 그림을 그려 이해 해보길 권장합니다.

 

6

 

7

 

8

 

 

---

 

피드백

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, 말씀해 주시면 감사하겠습니다.

읽어주셔서 감사합니다.