들어가며
능력있는 여자한테 장가가서
가정적인 남편이 되고 싶다.
행복한 꿈이자, 오랜 생각이다.
11.0 노드 기반 자료 구조
이어지는 챕터에서 다룰 다양한
자료구조는
모두 노드(node)라는 개념에
기반해 만들어졌다.
노드 기반 자료 구조는 데이터를
조직하고 접근하는
새로운 방법을 제공하는데,
성능상의 큰 이점이 많다.
11장에서는 가장 간단한 노드
기반 자료구조이자
이후 배울 내용의 기반인
연결 리스트를 살펴본다.
또한, 연결 리스트와 배열이 거의
같아 보이지만,
연결 리스트는 효율성 면에서
장단점(tade-off)이 있어
어떤 상황에서 성능이 크게
높아지는지도 알아보겠다.
11.1 연결 리스트
연결 리스트(linked list)는 배열과
마찬가지로,
항목의 리스트를 표현하는 자료 구조다.
사용자가 어떤 애플리케이션에서
배열을 사용 중이라면
아마도 배열 대신 연결 리스트를
쓰고 있을 가능성이 크다.
하지만 연결 리스트는 내부적으로
서로 다르게 구현되며
상황에 따라 성능이 다를 수 있다.
1장에서 설명했듯이 컴퓨터에
들어 있는 메모리는
데이터 조각을 저장하는 셀들의
거대한 집합 같은 형태다.
코드에서 배열을 생성하면
다음처럼 메모리 내에 연속된
빈 셀 그룹을 찾아
사용자 애플리케이션이 데이터를
저장할 수 있도록 할당한다.
| 9 | 16 | "a" | ||
| ■ | ■ | ■ | ■ | ■ |
| 100 | ||||
| 22 | "hi" |
컴퓨터는 배열 내 어떤 인덱스든
한 번에 접근할 수 있다고 설명했다.
즉, "인덱스 4에 있는 값을 찾아라"
라고 명령하는 코드를 작성하면
컴퓨터는 한 단계로 그 인덱스에
접근할 수 있다.
다시 말하지만 프로그램은 배열이
어떤 메모리 주소부터 시작하는지,
가령 메모리 주소 1000인지 알고
있으며, 인덱스 4를 찾고 싶으면
간단히 메모리 주소 1004로
접근하면 된다는 것을 안다.
이와 달리 연결 리스트는 나란히
이어진 메모리 셀 묶음이 아니다.
서로 인접하지 않은 메모리 셀
묶음으로 이뤄진다.
컴퓨터 메모리 전체에 걸쳐 여러
셀에 퍼져 있을 수도 있다.
서로 인접하지 않은 이러한 셀을
노드라 부른다.
그렇다면 큰 의문이 든다.
노드가 서로 인접해 있지 않다면
컴퓨터는 어떤 노드들이
같은 리스트에 속하는지 어떻게
알 수 있는가?
이 질문에 대한 답이 바로
연결 리스트의 핵심이다.
각 노드는 노드에 저장된 데이터뿐만
아니라,
연결 리스트 내에 다음 노드의
메모리 주소도 저장해야 한다.
| 주소값 |
주소값 |
주소값 |
주소값 |
||||||||||
| 1000 | 1001 | → | 1652 | 1653 | → |
1983 | 1984 | → |
2001 | 2002 | |||
| "a" | 1652 | ······ | "b" | 1983 | ······ |
"c" | 2001 | ······ |
"d" | null | |||
| (데이터) |
(링크) |
(데이터) |
(링크) |
(데이터) |
(링크) |
(데이터) |
(링크) |
||||||
위 예제를 보면,
연결 리스트에 "a", "b", "c", "d",
총 4개의 데이터가 있다.
하지만 데이터를 저장하는 데
각 노드마다 메모리 셀 2개씩,
총 메모리셀 8개를 사용한다.
첫 번째 셀에는 실제 데이터가
저장되어 있고,
두 번째 셀에는 다음 노드의
시작 메모리 주소를 뜻하는
링크가 저장되어 있다.
마지막 노드의 링크 부분에는
연결 리스트가 끝나므로 null이다.
연결 리스트를 다루는 코드는
항상 첫 번째 노드가 메모리의
어디에서 시작하는지 알아야 한다.
각 노드에는 다음 노드의 링크가
저장되어 있으므로
애플리케이션에 연결 리스트의
첫 번째 노드를 제공하면
첫 번째 노드에 있는 두 번째
노드의 링크를 따라서,
그리고 두 번째 노드에 있는
세 번째 노드의 링크를 따라서,
이후 계속해서 나머지 리스트를
조합할 수 있다.
연결 리스트가 배열보다 나은 점
중 하나는
프로그램이 데이터를 저장하기 위해
메모리 내에 나란히 이어진 빈 셀
묶음을 찾을 필요가 없다는 것이다.
프로그램은 서로 인접하지 않은
여러 셀에 걸쳐
데이터를 저장할 수 있다.
11.2 연결 리스트 구현
루비로 연결 리스트를 구현해 보자.
Node와 LinkedList라는 두 클래스를
사용해 구현하겠다.
먼저 Node 클래스를 만들어 보자.
|
1
2
3
4
5
6
7
8
9
|
class Node
attr_accessor :data, :next_node
def initialize(data)
@data = data
end
end
|
cs |
Node 클래스에는 속성이 2가지다.
노드에 저장해야 하는 값인 data와
리스트 내 다음 노드의 링크인
next_node다.
다음과 같이 Node 클래스를
사용한다.
|
1
2
3
4
5
6
7
8
9
|
node_1 = Node.new("once")
node_2 = Node.new("upon")
node_1.next_node = node_2
node_3 = Node.new("a")
node_2.next_node = node_3
node_4 = Node.new("time")
node_3.next_node = node_4
|
cs |
위 코드로 "once"와 "upon", "a",
"time"이라는 문자열을 포함하는
노드 4개짜리 리스트를 생성했다.
Node 클래스만 있어도 연결 리스트를
생성할 수 있지만,
프로그램에게 연결 리스트가
어디서부터 시작하는지
쉽게 알려줄 방법이 필요하다.
이를 위해 LinkedList 클래스를
생성하겠다.
다음은 기본적인 LinkedList 클래스다.
|
1
2
3
4
5
6
7
8
9
|
class LinkedList
attr_accessor :first_node
def initialize(first_node)
@first_node = first_node
end
end
|
cs |
LinkedList 클래스를 사용하면
다음 코드처럼 프로그램에게
앞서 생성한 연결 리스트를
알려줄 수 있다.
|
1
|
list = LinkedList.new(node_1)
|
cs |
LinkedList는 연결 리스트의
첫 번째 노드를 가리키므로
연결 리스트에 대한 핸들처럼
동작한다.
연결 리스트가 무엇인지 알았으니
전형적인 배열과 성능을 비교해보자.
대표적인 연산인 읽기와 검색, 삽입,
삭제를 분석해서 측정하겠다.
11.3. 읽기
앞서 강조했듯이 컴퓨터가 배열에서
값을 읽을 때는 한 단계,
즉 O(1) 만에 올바른 셀로 곧바로
갈 수 있다.
하지만 연결 리스트는 그렇지 않다.
프로그램이 연결 리스트의 인덱스
2에 있는 값을 읽을 때,
컴퓨터는 메모리 어디에서 찾아야
할지 바로 알 수 없으므로
한 단계만으로는 찾을 수 없다.
연결 리시트의 각 노드는 메모리
어디에든 있을 수 있기 때문이다.
프로그램은 연결 리스트의 첫 번째
노드의 메모리 주소만 알 뿐이다.
인덱스 2, 즉 세 번째 노드를
찾기 위해서는
프로그램은 연결 리스트의 인덱스
0부터 시작하여
인덱스 0에 있는 인덱스 1의 링크를
따라가고,
이어서 인덱스 1에 있는 인덱스 2의
링크를 따라간 후,
마지막으로 인덱스 2에 있는 값을
확인해야 한다.
LinkedList 클래스 내에 이러한
연산을 구현해 보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class LinkedList
attr_accessor :first_node
def initialize(first_node)
@first_node = first_node
end
def read(index)
# 리스트의 첫 번째 노드에서 시작한다.
current_node = first_node
current_index = 0
while current_index < index do
# 찾고 있는 인덱스에 도달할 때까지 각 노드의 링크를 계속 따라간다.
current_node = current_node.next_node
current_index += 1
# 리스트의 끝에 도착했다면 찾고 있는 값이 리스트에 없다는 뜻이므로
# null을 반환한다.
return nil unless current_node
end
return current_node.data
end
end
|
cs |
이제 다음 코드로 리스트 내의
특정 인덱스를 찾아볼 수 있다.
|
1
|
list.read(3)
|
cs |
컴퓨터가 어떤 인덱스에 있는 값을
찾을 때 최악의 시나리오는
리스트의 마지막 인덱스를 찾아보는 것이다.
이때 컴퓨터는 리스트의 첫 번째
노드부터 시작해서
마지막 노드에 다다를 때까지 각
링크를 따라가야 하므로
마지막 인덱스를 찾는데 N단계가
소요된다.
빅 오 표기법은 명시적으로 언급하지
않는 한 최악의 시나리오를 표현하므로
연결 리스트의 읽기 효율성은 O(N)이다.
배열의 읽기 효율성은 O(1)이므로,
상대적으로 심각한 단점이다.
11.4. 검색
배열과 연결 리스트는 검색 효율성이
같다.
검색은 리스트 내에서 어떤 데이터를
찾고 그 인덱스를 얻는 것이었다.
배열이든 연결 리스트든 프로그램은
검색하고 있는 값을 찾을 때까지
첫 번째 셀부터 시작해서 모든 셀을
하나씩 확인해야 한다.
만약 검색하고 있는 값이 마지막 셀에
있거나,
아예 리스트에 없는 최악의 시나리오라면
O(N) 단계가 걸린다.
다음과 같이 검색 연산을 구현할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class LinkedList
attr_accessor :first_node
def initialize(first_node)
@first_node = first_node
end
# 읽기 코드 생략
def index_of(value)
# 리스트의 첫 번째 노드에서 시작
current_node = first_node
current_index = 0
begin
# 찾고 있던 데이터를 찾았으면 반환한다.
if current_node.data == value
return current_index
end
# 그렇지 않으면 다음 노드로 이동한다.
current_node = current_node.next_node
current_index += 1
end while current_node
# 데이터를 찾지 못한 재 전체 리스트를 순회했으면 null을 반환한다.
return nil
end
end
|
cs |
이제 다음 코드로 리스트 내의
어떤 값이든 검색할 수 있다.
|
1
|
list.index_of("time")
|
cs |
11.5 삽입
연결 리스트가 배열에 비해
어떤 상황에서 뚜렷한 장점을
보일 수 있는 연산이 삽입이다.
배열 삽입에서 최악의 시나리오는
프로그램이 인덱스 0에 데이터를
삽입할 때였다.
나머지 데이터를 한 셀씩 오른쪽으로
옮겨야 하므로 효율성이 O(N)이었다.
반면 연결 리스트는 리스트(노드) 앞에
삽입하는데 딱 한단계, O(1)만 소요된다.
이유를 알아보자.
다음과 같은 연결 리스트가
있다고 하자.
"black"을 리스트 앞에 삽입하려면
새 노드를 생성하고,
노드가 "blue"를 포함하는 노드를
가리키게끔 하면 된다.
따라서 배열과 달리 연결 리스트에는
데이터를 하나도 시프트하지 않고
리스트 앞에 데이터를 삽입할 수
있는 유연성이 있다.
이론적으로는 데이터를 연결 리스트
내부의 어디에 삽입하든
딱 한 단계만 걸리지만 한 가지
알아둘 점이 있다.
연결 리스트는 이제 다음과
같아졌다.
"white"를 인덱스 2*에 삽입해보자.
* "blue"와 "green"의 사이
다음 그림처럼
새 노드를 생성하고 블루와
그린 노드의 링크를 수정한다.
따라서 실제 삽입은 한 단계가
소요된다.
문제는 컴퓨터가 이렇게 하려면
인덱스 1에 있는 노드
즉 "blue" 데이터를 담고 있는
노드를 찾아야만
그 노드의 링크가 새로 생성된
노드를 가리키도록
수정할 수 있다는 것이다.
어떻게 동작하는지 보자.
새 노드를 인덱스 1 뒤에 추가하려 한다.
따라서 컴퓨터는 리스트에서
인덱스 1을 찾아야 한다.
이렇게 하려면 리스트 앞에서부터
시작해야 한다.
이어서 첫 번째 링크를 따라
다음 노드에 접근한다.
인덱스 1을 찾았으므로 이제
새 노드를 추가할 수 있다.
위 경우, "white"를 추가하는 데
3단계가 걸렸다.
리스트 끝에 추가했다면,
인덱스 3을 찾는 4단계와 새 노드를
삽입하는 1단계,
총 5단계가 소요됐을 것이다.
결국 연결 리스트의 중간에 삽입할
때는 배열과 마찬가지로 O(N)이 걸린다.
흥미롭게도 위 분석을 통해 배열과
연결 리스트의
최선과 최악의 시나리오가 정확히
서로 정반대임을 알 수 있다.
즉, 앞에 삽입은 연결 리스트가
훌륭한 효율성을 가진 반면
배열은 가장 효율성이 나쁘다.
끝에 삽입의 경우 배열에서는
최선의 시나리오지만
연결 리스트에서는 최악의 경우다.
상황별로 정리하면 다음과 같다.
다음처럼 LinkedList 클래스 내에
삽입 연산을 구현할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class LinkedList
attr_accessor :first_node
def initialize(first_node)
@first_node = first_node
end
# 읽기 코드 생략
# 검색 코드 생략
def insert_at_index(index, value)
current_node = first_node
current_index = 0
# 먼저 삽입하려는 새 노드의 바로 앞 인덱스를 찾는다.
while current_index < index do
current_node = current_node.next_node
current_index += 1
end
# 새 노드를 생성한다.
new_node = Node.new(value)
new_node.next_node = current_node.next_node
# 새 노드를 가리키도록 앞 노드의 링크를 수정한다.
current_node.next_node = new_node
end
end
|
cs |
11.6. 삭제
효율성 면에서 삭제는 삽입과
매우 유사하다.
연결 리스트 앞에서 노드를
삭제하려면 한 단계면 된다.
연결 리스트의 first_node가 2번째
노드를 가리키게 하면 된다.
"once", "upon", "a", "time" 값을
포함하는
연결 리스트 예제로 돌아가 보자.
"once"를 삭제하고 싶으면 "upon"에서
시작하도록 연결 리스트를 바꾸면 된다.
|
1
|
list = LinkedList.new(node_1)
|
cs |
이와 달리 배열은 첫 번째 원소를
삭제하면
나머지 데이터를 모두 한 셀씩
왼쪽으로 시프트해야 하므로
효율성이 O(N)이다.
연결 리스트에서 마지막 노드를
삭제하는 경우
실제 삭제에는 한 단계가 걸린다.
끝에서 두 번째 노드를 가져와
링크를 null로 만들면 된다.
하지만 끝에서 두 번째 노드를
가져오려면
리스트 앞에서부터 시작해서 끝까지
링크를 따라가야 하므로 N단계가 걸린다.
다음 표는 배열과 연결 리스트의
다양한 삭제 시나리오를 대조한다.
삽입과 정말 똑같다.
리스트 중간에서 삭제하려면,
컴퓨터는 앞 노드의 링크를
수정해야 한다.
다음 예제로 명확하게 이해할 수 있다.
앞서 본 연결 리스트에서 인덱스 2에
있는 값을 삭제할 것이다.
컴퓨터는 인덱스 1을 찾아서 "green"
노드를 가리키도록 링크를 변경한다.
LinkedList 클래스 내에서의 삭제
연산은 다음과 같을 것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
class LinkedList
attr_accessor :first_node
def initialize(first_node)
@first_node = first_node
end
# 읽기 코드 생략
# 검색 코드 생략
# 삽입 코드 생략
def delete_at_index(index)
current_node = first_node
current_index = 0
# 먼저 삭제하려는 노드의 바로 앞 인덱스를 찾아 current_node에 할당한다.
while current_index < index - 1 do
current_node = current_node.next_node
current_index += 1
end
# 삭제하려는 노드의 바로 뒤 노드를 찾는다
# current_node의 다음 노드(삭제할 )의 다음 노드
node_after_deleted_node = current_node.next_node.next_node
# current_node의 링크가 node_after_deleted_node를 가리키도록 수정한다.
# 이렇게 하면 삭제하려는 노드가 리스트에서 제외된다.
current_node.next_node = node_after_deleted_node
end
end
|
cs |
연결 리스트와 배열을 분석해서
비교해 보면
다음과 같이 분류된다.
검색과 삽입, 삭제는 차이가 거의
없는 듯 보이고
배열 읽기만 연결 리스트 읽기보다
훨씬 빠르다.
그렇다면 누가 연결 리스트를
사용하려고 할까?
11.7. 연결 리스트 다뤄보기
연결 리스트가 빛을 발하는 경우는
한 리스트를 검사해서 많은 원소를
삭제할 때다.
예를 들어 이메일 주소 리스트를
샅샅이 검토해서
유효하지 않은 형식의 이메일을
모두 삭제하는
애플리케이션을 만든다고 하자.
이 알고리즘은 한 번에 하나씩 모든
이메일 주소를 검사하고,
정규식*을 사용해 이메일 주소가
유효하지 않은지 확인한다.
* 어떤 유형의 데이터를 식별하는 특수한 패턴
유효하지 않으면 리스트에서 제거한다.
리스트가 배열이든 연결 리스트든
전체 리스트를 한 번에 한 원소씩
살펴보며 각 값을 검사해야 하므로
N단계가 걸린다.
하지만 실제로 이메일 주소를 삭제할
때 어떻게 되는지 보자.
배열에서는 이메일 주소를 삭제할
때마다 빈 공간을 매꾸기 위해
나머지 데이터를 왼쪽으로 시프트해야
하는 또 다른 O(N) 단계가 필요하다.
모든 시프트는 다음 이메일 주소를
검사하기도 전에 일어난다.
따라서 각 이메일 주소를 읽는
N단계 외에
유효하지 않은 이메일 주소를
삭제하는 데 필요한 단계인
유효하지 않은 이메일 주소의
개수 * N단계가 추가로 걸린다.
이메일 주소 열 개 중 하나가
유효하지 않다고 가정하자.
이메일 주소 1000개로 이뤄진
리스트가 있을 때
약 100개의 유효하지 않은
이메일이 있을 것이고,
따라서 알고리즘은 읽기 1000단계
+ 삭제 약 100,000 단계*가 걸릴 것이다.
* 유효하지 않은 이메일 100개 * 각 이메일 주소를 읽는 N단계
하지만 연결 리스트에서는
리스트 전체를 살펴보면서
삭제가 필요하면 그저 그 노드의
링크가
적절한 노드를 가리키도록
바꾸면 되므로
각 삭제마다 딱 한 단계가
걸린다.
이메일이 천 개 있을 때,
알고리즘은 1,000개의 읽기 단계와
100개의 삭제 단계,
딱 1,100단계만 걸린다.
11.8. 이중 연결 리스트
연결 리스트를 흥미롭게 응용하는
한 가지 사례가
큐의 내부 자료 구조로 사용하는
것이다.
8장 스택과 큐로 간결한 코드 생성에서
다뤄봤던 큐는
데이터를 끝에만 삽입할 수 있고
앞에서만 삭제할 수 있는
그러한 성격을 가진 항목들의
리스트였다.
8장에서는 큐가 단지 특수한 제약을
갖는 배열임을 설명하면서
배열을 큐의 기반으로 사용했다.
하지만 연결 리스트 역시
동일한 제약*을 가하면 큐의 기반으로
사용할 수 있다.
* 끝에서만 데이터를 삽입하고 앞에서만 데이터를 삭제할 수 있는 큐의 고유한 제약
배열 대신 연결 리스트를 쓰면
좋은 점이 있을까?
분석해 보자.
다시 말하지만 큐는 데이터를
리스트 끝에 삽입한다.
11장에서 앞서 논했듯이,
끝에서 데이터 삽입은 효율성이
O(1)인 배열이 더 낫다.
연결 리스트는 O(N)에 데이터를
삽입한다.
따라서 삽입 측면에서는 배열이
연결 리스트보다 나은 선택이다.
하지만 큐에서의 데이터 삭제는
앞에서부터 데이터를 삭제하는 데
O(N)이 걸리는 배열과 달리
O(1)이 걸리는 연결 리스트가
훨씬 더 빠르다.
이러한 분석에 따르면 주요한
연산 중 하나가 O(1)이고
나머지는 O(N)이므로 배열을
쓰든 연결 리스트를 쓰든
상관이 없어 보인다.
배열에서는 삽입이 O(1)이고
삭제가 O(N)이며,
연결 리스트에서는 삽입이 O(N)이고
삭제가 O(1)이다.
하지만 이중 연결 리스트라는 특수한
연결 리스트의 변형을 사용하면
큐에서의 데이터 삽입과 삭제를
모두 O(1)에 할 수 있다.
이중 연결 리스트는 각 노드에
링크가 2개라는 점만 제외하면
연결 리스트와 비슷하다.
한 링크는 다음 노드를 가리키고,
다른 한 링크는 앞 노드를 가리킨다.
그뿐만 아니라 이중 연결 리스트는
처음과 마지막 노드를 모두 기록한다.
이중 연결 리스트는 다음처럼 생겼다.
코드로 살펴보면 이중 연결 리스트의
핵심부는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Node
attr_accessor :data, :next_node, :previous_node
def initialize(data)
@data = data
end
end
class DoublyLinkedList
attr_accessor :first_node, :last_node
def initialize(first_node=nil, last_node=nil)
@first_node = first_node
@last_node = last_node
end
end
|
cs |
이중 연결 리스트는 항상 첫 노드와
마지막 노드를 모두 알고있으므로
각각 한 단계, 즉 O(1)에 접근할 수 있다.
유사하게 다음과 같은 방식으로
한 단계만에 이중 연결 리스트 끝에
데이터를 삽입할 수 있다.
새 노드("white")를 생성해서
이 노드의 previous_node가
연결리스트의 last_node("red")를
가리키도록 한다.
이어서 last_node("red")의 next_node가
새 노드("white")를 가리키도록 한다.
끝으로 새 노드("white")를
이 연결리스트의 last_node로 선언한다.
다음은 이중 연결 리스트에 쓸 수 있는
새로운 insert_at_end 메서드 구현이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class DoublyLinkedList
attr_accessor :first_node, :last_node
def initialize(first_node=nil, last_node=nil)
@first_node = first_node
@last_node = last_node
end
def insert_at_end(value)
new_node = Node.new(value)
# 연결 리스트에 아직 원소가 없을 때
if !first_node
@first_node = new_node
@last_node = new_node
else
new_node.previous_node = @last_node
@last_node.next_node = new_node
@last_node = new_node
end
end
end
|
cs |
이중 연결 리스트는,
리스트의 앞과 끝 모두에 바로
접근할 수 있으므로
O(1)에 양 끝에 데이터를 삽입할
수 있을 뿐만 아니라
O(1)에 양 끝에서 데이터를 삭제할
수 있다.
이중 연결 리스트는 O(1) 시간에
리스트 끝에 데이터를 삽입하고
O(1) 시간에 리스트 앞에 데이터를
삭제할 수 있으므로
큐를 위한 완벽한 내부 자료 구조다.
다음은 이중 연결 리스트를 기반으로
한 완전한 큐 예제다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
class Node
attr_accessor :data, :next_node, :previous_node
def initialize(data)
@data = data
end
end
class DoublyLinkedList
attr_accessor :first_node, :last_node
def initialize(first_node=nil, last_node=nil)
@first_node = first_node
@last_node = last_node
end
def insert_at_end(value)
new_node = Node.new(value)
# 연결 리스트에 원소가 아직 없을 때
if !first_node
@first_node = new_node
@last_node = new_node
else
new_node.previous_node = @last_node
@last_node.next_node = new_node
@last_node = new_node
end
end
def remove_from_front
removed_node = @first_node
@first_node = @first_node.next_node
return removed_node
end
end
class Queue
attr_accessor :queue
def initialize
@queue = DoublyLinkedList.new
end
def enque(value)
@queue.insert_at_end(value)
end
def deque
removed_node = @queue.remove_from_front
return removed_node.data
end
def tail
return @queue.last_node.data
end
end
|
cs |
11.9. 마무리
현재 작성 중인 애플리케이션에
큐가 필요 없을 수도 있고,
현재 사용 중인 큐가 이중 연결
리스트가 아닌
배열 기반 큐라도 잘 동작할 수 있다.
하지만 선택의 기회가 있음을 알리고,
적시에 올바른 선택을 하는 방법을 익혀두자.
연결 리스트가 특정 상황에서 성능
향상에 얼마나 유용한지 배웠다.
12장에서는 훨씬 보편적이면서
여러 일상적인 상황에서
애플리케이션을 더욱 효율적으로
실행시키는
좀 더 복잡한 노드 기반 자료 구조를
배우겠다.
참고 및 출처
 |
|
