제 2장 연결리스트

리스트 일반적인 리스트(List)는 일련의 동일한 타입의 항목(item)들 실생활의 예: 학생 명단, 시험 성적, 서점의 신간 서적, 상점의 판매 품목, 실시간 급상승 검색어, 버킷 리스트 등 일반적인 리스트의 구현: 1차원 파이썬 리스트(list) 단순연결리스트 이중연결리스트 원형연결리스트

2.1 단순연결리스트 단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조 동적 메모리 할당을 받아 노드(node)를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킴

연결리스트에서는 삽입이나 삭제 시 항목들의 이동이 필요 없음 배열(자바, C, C++언어)의 경우 최초에 배열의 크기를 예측하여 결정해야 하므로 대부분의 경우 배열에 빈 공간을 가지고 있으나, 연결리스트는 빈 공간이 존재하지 않음 연결리스트에서는 항목을 탐색하려면 항상 첫 노드부터 원하는 노드를 찾을 때까지 차례로 방문하는 순차탐색(Sequential Search)을 해야

단순연결리스트를 위한 SList 클래스

[그림 2-2] insert_front() 함수 head (a) 새 노드 삽입 전 head ② x ① ② (b) 새 노드 삽입 후 [그림 2-2] insert_front() 함수

[그림 2-3] insert_after() 함수 p head (a) 새 노드 삽입 전 p head ② x ① ② (b) 새 노드 삽입 후 [그림 2-3] insert_after() 함수

[그림 2-4] delete_front() 함수 head (a) 첫 노드 삭제 전 head ① x ① (b) 첫 노드 삭제 후 [그림 2-4] delete_front() 함수

[그림 2-5] delete_after() 함수 p head … (a) 노드 삭제 전 p t ① head ② … x ② (b) 노드 삭제 후 [그림 2-5] delete_after() 함수

[프로그램 2-2] main.py

[프로그램 2-1, 2]의 수행 결과

단순연결리스트는 매우 광범위하게 활용되는데, 그 중에 3장의 스택과 큐 자료구조 6장 해싱의 체이닝(Chaining)에 사용 4장의 트리도 단순연결리스트의 개념을 확장시킨 자료구조

수행시간 search()는 탐색을 위해 연결리스트의 노드들을 첫 노드부터 순차적으로 방문해야 하므로 O(N) 시간 소요 삽입이나 삭제 연산은 각각 O(1) 개의 레퍼런스만을 갱신하므로 O(1) 시간 소요 단, insert_after()나 delete_after()의 경우에 특정 노드 p의 레퍼런스가 주어지지 않으면 head로부터 p를 찾기 위해 search()를 수행해야 하므로 O(N) 시간 소요

2.2 이중연결리스트 이중연결리스트(Doubly Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드와 다음 노드를 가리키는 연결리스트 단순연결리스트는 삽입이나 삭제할 때 반드시 이전 노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 노드들을 탐색할 수 없음 이중연결리스트는 단순연결리스트의 이러한 단점을 보완하나, 각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가짐

이중연결리스트를 위한 DList 클래스

[프로그램 2-3] dlist.py

header tail   [그림 2-8] DList 객체 생성

[그림 2-9] insert_before()의 삽입 수행 p newNode ④ ⑤ ② ③ ⑥ ⑤ t x p ① x ⑥ [그림 2-9] insert_before()의 삽입 수행

[그림 2-10] insert_after()의 삽입 수행 p newNode ④ ⑤ ② ③ ⑥ ⑤ p x t x ① ⑥ [그림 2-10] insert_after()의 삽입 수행

x x f r ① ④ ② ④ x x ③ ③ [그림 2-11] delete()의 삭제 수행

[프로그램 2-4] main.py

[프로그램 2-3, 4] 수행 결과

수행시간 이중연결리스트에서 삽입이나 삭제 연산은 각각 상수 개의 레퍼런스만을 갱신하므로 O(1) 시간에 수행 탐색 연산: head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 시간 소요

이중연결리스트는 3장의 데크(Deque) 자료구조를 구현하는데 사용 이항힙(Binomial Heap)이나 피보나치힙(Fibonacci Heap)과 같은 우선순위큐를 구현하는 데에도 이중연결리스트가 부분적으로 사용

2-3 원형연결리스트 원형연결리스트(Circular Linked List)는 마지막 노드가 첫 노드와 연결된 단순연결리스트 원형연결리스트에서는 마지막 노드의 레퍼런스가 저장된 last가 단순연결리스트의 head와 같은 역할

마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있는 장점 리스트가 empty가 아니면 어떤 노드도 None 레퍼런스를 가지고 있지 않으므로 프로그램에서 None 조건을 검사하지 않아도 되는 장점 원형연결리스트에서는 반대 방향으로 노드들을 방문하기 쉽지 않으며, 무한 루프가 발생할 수 있음에 유의할 필요

원형연결리스트를 위한 CList 클래스

[프로그램 2-5] clist.py

[그림 2-14] insert()의 노드 삽입 newNode ① ③ last last ②

[그림 2-15] delete()의 노드 삭제 x ① ② last ② x last last …

[프로그램 2-6] main.py

[프로그램 2-5, 6]의 수행 결과

여러 사람이 차례로 돌아가며 하는 게임을 구현하는데 적합한 자료구조 많은 사용자들이 동시에 사용하는 컴퓨터에서 CPU 시간을 분할하여 작업들에 할당하는 운영체제에 사용 이항힙(Binomial Heap)이나 피보나치힙(Fibonacci Heap)과 같은 우선순위큐를 구현하는 데에도 원형연결리스트가 부분적으로 사용

수행시간 원형연결리스트에서 삽입이나 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1) 시간에 수행 탐색 연산: last로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 소요

요약 리스트: 일련의 동일한 타입의 항목들 단순연결리스트: 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조 단순연결리스트에서는 삽입이나 삭제 시 항목들을 이동시킬 필요 없음 단순연결리스트는 항목을 접근하기 위해서 순차탐색을 해야 하고, 삽입이나 삭제할 때에 반드시 이전 노드를 가리키는 레퍼런스를 알아야 함

이중연결리스트는 각 노드에 2 개의 레퍼런스를 가지며 각각 이전 노드와 다음 노드를 가리키는 방식의 연결리스트 원형연결리스트는 마지막 노드가 첫 노드와 연결된 단순연결리스트 원형연결리스트는 마지막 노드와 첫 노드를 O(1) 시간에 방문. 또한 리스트가 empty가 아닐 때, 어떤 노드도 None 레퍼런스를 갖지 않으므로 프로그램에서 None 조건을 검사하지 않아도 되는 장점

최악경우 수행시간 비교 제 3장 스택과 큐

제 3장 스택과 큐

3.1 스택 한 쪽 끝에서만 item(항목)을 삭제하거나 새로운 item을 저장하는 자료구조 새 item을 저장하는 연산: push Top item을 삭제하는 연산: pop 후입 선출(Last-In First-Out, LIFO) 원칙 하에 item의 삽입과 삭제 수행

[그림 3-2] 스택의 push와 pop 연산

top top 1 2 3 1 2 3 [그림 3-3] 리스트로 구현된 스택

리스트로 구현한 스택

[프로그램 3-1]

단순연결리스트로 구현한 스택

[프로그램 3-2]

수행시간 파이썬의 리스트로 구현한 스택의 push와 pop 연산은 각각 O(1) 시간이 소요 파이썬의 리스트는 크기가 동적으로 확대 또는 축소되며, 이러한 크기 조절은 사용자도 모르게 수행된다. 이러한 동적 크기 조절은 스택(리스트)의 모든 항목들을 새 리스트로 복사해야 하기 때문에 O(N) 시간이 소요 단순연결리스트로 구현한 스택의 push와 pop 연산은 각각 O(1) 시간 연결리스트의 맨 앞 부분에서 노드를 삽입하거나 삭제하기 때문

3.2 스택의 응용 컴파일러의 괄호 짝 맞추기 회문(Palindrome) 검사하기

컴파일러의 괄호 짝 맞추기 [핵심 아이디어] 왼쪽 괄호는 스택에 push, 오른쪽 괄호를 읽으면 pop 수행 모든 괄호를 읽은 뒤 에러가 없고 스택이 empty이면, 괄호들이 정상적으로 사용된 것 만일 모든 괄호를 처리한 후 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것이므로 에러 처리

[예제 1]

          { ( ) { ( ) ) }  (  ) ( )   ( { (  {  { {  [예제 2]         { ( ) { ( ) ) }  (   ) (  )   ( {  (  {  { {  { { { { { { { empty push({) push(() pop() push({) push(() pop() pop()

회문 검사하기 회문(Palindrome): 앞으로부터 읽으나 뒤로부터 읽으나 동일한 스트링 [핵심 아이디어] 전반부의 문자들을 스택에 push한 후, 후반부의 각 문자를 차례로 pop한 문자와 비교 회문 검사하기는 주어진 스트링의 앞부분 반을 차례대로 읽어 스택에 push한 후, 문자열의 길이가 짝수이면 뒷부분의 문자 1 개를 읽을 때마다 pop하여 읽어 들인 문자와 pop된 문자를 비교하는 과정을 반복 수행 만약 마지막 비교까지 두 문자가 동일하고 스택이 empty가 되면, 입력 문자열은 회문

A B S A B S S B A =             문자열의 길이가 홀수인 경우, 주어진 스트링의 앞부분 반을 차례로 읽어 스택에 push한 후, 중간 문자를 읽고 버린다. 이후 짝수 경우와 동일하게 비교 수행 [예제 1] A B S A B S S B A = pop() push(A) push(B) push(S)             empty

       R A C E C A R  E  C = C  C C  A = A  A A A A  R = [예제 2]        R A C E C A R  E  C = C  C C  A = A  A A A A  R = R  R R R R R R empty push(R) push(A) push(C) pop() pop() pop()

스택의 기타 응용 후위표기법(Postfix Notation) 수식 계산하기 중위표기법(Infix Notation) 수식의 후위표기법 변환 미로 찾기 트리의 방문(4장) 그래프의 깊이우선탐색(8장) 프로그래밍에서 매우 중요한 함수/메소드 호출 및 재귀호출도 스택 자료구조를 바탕으로 구현

수식의 표기법 [연습문제] 프로그램을 작성할 때 수식에서 +, –, *, /와 같은 이항연산자는 2개의 피연산자들 사이에 위치 프로그램을 작성할 때 수식에서 +, –, *, /와 같은 이항연산자는 2개의 피연산자들 사이에 위치 이러한 방식의 수식 표현이 중위표기법(Infix Notation) 컴파일러는 중위표기법 수식을 후위표기법(Postfix Notation)으로 바꾼다. 그 이유는 후위표기법 수식은 괄호 없이 중위표기법 수식을 표현할 수 있기 때문 전위표기법(Prefix Notation): 연산자를 피연산자들 앞에 두는 표기법

중위표기법 수식과 대응되는 후위표기법, 전위표기법 수식 [연습문제] 중위표기법 수식과 대응되는 후위표기법, 전위표기법 수식 중위표기법 후위표기법 전위표기법 A + B A B + + A B A + B – C A B + C – + A – B C A + B * C – D A B C * + D – – + A * B C D (A + B) / (C – D) A B+ C D – / / + A B – C D

후위표기법 수식 계산 후위표기법으로 표현된 수식 계산 알고리즘 [연습문제] 후위표기법 수식 계산 [핵심 아이디어] 피연산자는 스택에 push하고, 연산자는 2회 pop하여 계산한 후 push 후위표기법으로 표현된 수식 계산 알고리즘 입력을 좌에서 우로 문자를 한 개씩 읽는다. 읽은 문자를 C라고하면 [1] C가 피연산자이면 스택에 push [2] C가 연산자(op)이면 pop을 2회 수행한다. 먼저 pop된 피연산자가 A이고, 나중에 pop된 피연산자가 B라면, (A op B)를 수행하여 그 결과 값을 push

[예제]        8 3 2 + 1 – /   3 + 2 = 5 5 – 1 = 4 2 1    [연습문제]        8 3 2 + 1 – /   3 + 2 = 5 5 – 1 = 4 2 1    8 / 4= 2  3 3 5 5 4  8 8 8 8 8 8 2 2 empty push(8) push(3) push(2) pop() push(1) pop() pop() pop() pop() pop() pop() push(5) push(4) push(2)

중위표기법 수식을 후위표기법으로 변환 [연습문제] [핵심 아이디어] 왼쪽 괄호나 연산자는 스택에 push하고, 피연산자는 출력 입력을 좌에서 우로 문자를 1개씩 읽는다. 읽은 문자가 피연산자이면, 읽은 문자를 출력 왼쪽 괄호이면, push 오른쪽 괄호이면, 왼쪽 괄호가 나올 때까지 pop하여 출력. 단, 오른쪽이나 왼쪽 괄호는 출력하지 않음 연산자이면, 자신의 우선순위보다 낮은 연산자가 스택 top에 올 때까지 pop하여 출력하고 읽은 연산자를 push 입력을 모두 읽었으면 스택이 empty될 때까지 pop하여 출력

[연습문제] [예제]

3.3 큐 큐(Queue): 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조 일상생활의 관공서, 은행, 우체국, 병원 등에서 번호표를 이용한 줄서기가 대표적인 큐 선입 선출(First-In First-Out, FIFO) 원칙 하에 item의 삽입과 삭제 수행

파이썬 리스트로 구현한 큐

[프로그램 3-3]

단순연결리스트로 구현한 큐

[프로그램 3-4]

CPU의 태스크 스케줄링(Task Scheduling) 네트워크 프린터 실시간(Real-time) 시스템의 인터럽트(Interrupt) 처리 다양한 이벤트 구동 방식(Event-driven) 컴퓨터 시뮬레이션 콜 센터의 전화 서비스 처리 등 4장의 이진트리의 레벨순회(Level-order Traversal) 8장의 그래프에서 너비우선탐색(Breath-First Search) 등

수행시간 리스트로 구현한 큐의 add와 remove 연산은 각각 O(1) 시간이 소요 하지만 리스트 크기를 확대 또는 축소시키는 경우에 큐의 모든 항목들을 새 리스트로 복사해야 하므로 O(N) 시간이 소요 단순연결리스트로 구현한 큐의 add와 remove 연산은 각각 O(1) 시간 삽입 또는 삭제 연산이 rear 와 front로 인해 연결리스트의 다른 노드들을 일일이 방문할 필요 없이 각 연산이 수행되기 때문

3.4 데크 데크(Double-ended Queue, Deque): 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조 데크는 스택과 큐 자료구조를 혼합한 자료구조 따라서 데크는 스택과 큐를 동시에 구현하는데 사용

스크롤(Scroll) 문서 편집기 등의 undo 연산 웹 브라우저의 방문 기록 등 - 웹 브라우저 방문 기록의 경우, 최근 방문한 웹 페이지 주소는 앞에 삽입하고, 일정 수의 새 주소들이 앞쪽에서 삽입되면 뒤에서 삭제가 수행

데크를 이중연결리스트로 구현하는 것이 편리 단순연결리스트는 rear가 가리키는 노드의 이전 노드의 레퍼런스를 알아야 삭제가 가능하기 때문

파이썬에는 데크가 Collections 패키지에 정의되어 있음 삽입, 삭제 등의 연산은 파이썬의 리스트의 연산들과 매우 유사

수행시간 데크를 배열이나 이중연결리스트로 구현한 경우, 스택과 큐의 수행시간과 동일 데크를 배열이나 이중연결리스트로 구현한 경우, 스택과 큐의 수행시간과 동일 양 끝에서 삽입과 삭제가 가능하므로 프로그램이 다소 복잡 이중연결리스트로 구현한 경우는 더 복잡함

요약 스택은 한 쪽 끝에서만 item을 삭제하거나 새로운 item을 저장하는 후입선출(LIFO) 자료구조 스택은 컴파일러의 괄호 짝 맞추기, 회문 검사하기, 후위표기법수식 계산하기, 중위표기법 수식을 후위표기법으로 변환하기, 미로 찾기, 트리의 노드 방문, 그래프의 깊이우선탐색에 사용. 또한 프로그래밍에서 매우 중요한 메소드 호출 및 재귀호출도 스택 자료구조를 바탕으로 구현 큐는 삽입과 삭제가 양 끝에서 각각 수행되는 선입선출(FIFO) 자료구조

큐는 CPU의 태스크 스케줄링, 네트워크 프린터, 실시간 시스템의 인터럽트 처리, 다양한 이벤트 구동 방식 컴퓨터 시뮬레이션, 콜 센터의 전화 서비스 처리 등에 사용되며, 이진트리의 레벨순회와 그래프의 너비우선탐색에 사용 데크는 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조로서 스택과 큐 자료구조를 혼합한 자료구조 데크는 스크롤, 문서 편집기의 undo 연산, 웹 브라우저의 방문 기록 등에 사용

스택, 큐, 데크의 수행시간 비교 