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

안녕하세요.

공상 개발입니다.

 

이번 시간에는 저번 연결 리스트(linked list) 리뷰를 이어서,

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

이중 연결 리스트(Doubled Linked List)에 대해 간단히 알아보는 시간을 갖겠습니다.

 

 

---

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

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

 

3. 연결 리스트(Linked List)로 구현한 큐(Queue) 프로그램

 

*Data Structure - linked list(Vol.1)을 먼저 읽어보시는 걸 추천합니다.

 

---

 

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

 

 

 

큐와 마찬가지로 연결 리스트도 원형으로 구현이 가능합니다.

기본적인 형태는 마지막 노드의 링크가 첫 번째 노드를 가리키게 구현합니다.

 

이와는 다르게 

 

헤드 포인터가 마지막 노드를 가리키게 구현한 경우도 있습니다.

리스트의 삽입 연산을 첫 번째와 마지막 노드에서 편하게 구현하기 위해서입니다.

목적에 따라 원하는 구현 방법을 선택하시면 됩니다.

 

원형 연결 리스트 - 마지막 노드의 링크가 첫 번 째 노드를 가리키는 리스트 - 한 노드에서 다른 모든 노드로의 접근이 가능

 

변형된 원형 연결 리스트 - 보통 헤드포인터가 마지막 노드를 가리키게끔 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이   단순 연결 리스트에 비하여 용이

 

변형된 원형 연결 리스트

 

 

* 이해를 위한 이미지와 구현 코드

 

원형 연결 리스트의 경우 지난 Vol.1에서 다루었던 연결 리스트의 개념에 대해 이해하고 계신다면,

이미지와 함께 소스 코드를 보신다면 이해에 있어 큰 어려움이 없을 거라고 생각합니다.

 

아래의 이미지들을 보신다면 앞에서 보았던 변형된 원형 연결 리스트의 형태를 보입니다.

헤드 포인터가 마지막 노드를 가리킵니다.

 

1

 

 

2

 

---

 

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

 

* 설명이 많습니다.

 

 

이중 연결 리스트는 처음 접하신다면 헷갈릴 수도 있습니다.

반복 숙달이 정답이라고 생각합니다.

천천히 보시면서 어떻게 동작할지 생각하는 걸 추천합니다.

 

이중 연결 리스트 - 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트 - 단점은 공간을 많이 차지하고 코드가 복잡 - 헤드 노드와 함께 원형 연결 리스트를 혼합한 형태로 많이 사용됨 (삽입/삭제 알고리즘을 간편하게 하기 위해) 헤드 노드 - 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드 - 헤드 포인터와의 구별 필요 - 공백상태에서는 헤드 노드만 존재

 

이중 연결 리스트

 

노드를 이중 연결 리스트로 구현한 소스 코드

 

지금까지 봐온 연결 리스트들과 다른 형태를 볼 수 있습니다.

바로 링크를 2개 가진다는 점입니다. 이는 선행 노드와 후속 노드에 접근하기 위한 것입니다.

 

 

아마 위에 있었던 이중 연결 리스트 에서

헤드 노드와 마지막 노드가 어떻게 연결이 되는지 고민되실 거라 생각합니다.

 

같이 생각해봅시다.

 

1. 헤드 노드와 마지막 노드 둘 다 연결되는 링크는 2개.

2. 헤드 노드의 왼쪽 링크는 마지막 노드를 오른쪽 링크는 후속 노드를 가리킵니다.

3. 마지막 노드의 왼쪽 링크는 선행 노드를 오른쪽 링크는 헤드 노드를 가리킵니다.

 

헷갈리는 이유

 

변형된 원형 연결 리스트의 형태는 헤드 포인터가 마지막 노드를 가리킨다고 말했습니다.

그런데

이중 연결 리스트에서는 선행 노드와 후속 노드 양쪽을 다 연결하니까

헤드 포인터만 마지막 노드를 가리키는 것이 아닌,

마지막 노드도 헤드 포인터를 가리키게 구현한 것입니다.

 

 

삽입 연산

 

 

삭제 연산

 

 

* 이중 연결 리스트 테스트 프로그램 소스 코드

 

전체적인 구현 흐름을 보고 싶어 하시는 분들이 있어서 올려드렸습니다.

 

이중 연결 리스트 테스트 프로그램

 

---

 

연결 리스트로 큐를 구현할 수 있다고 했는데 어떻게 구현할까요?

아래의 이미지와 소스코드를 보고 직접 코드를 구현해보는 걸 추천합니다.

 

연결 리스트로 구현한 큐

# 크기가 제한되지 않는다.

 

 

삽입연산

 

삭제연산

 

 

연결 리스트로 구현한 간단한 큐 프로그램

 

 

---

 

피드백

 

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

읽어주셔서 감사합니다.