제 2 장연결리스트
리스트 일반적인리스트 (List) 는일련의동일한타입의항목 (item) 들 실생활의예 : 학생명단, 시험성적, 서점의신간서적, 상점의판매품목, 실시간급상승검색어, 버킷리스트등 일반적인리스트의구현 : - 1 차원파이썬리스트 (list) - 단순연결리스트 - 이중연결리스트 - 원형연결리스트
2.1 단순연결리스트 단순연결리스트 (Singly Linked List) 는동적메모리할당을이용해리스트를구현하는가장간단한형태의자료구조 동적메모리할당을받아노드 (node) 를저장하고, 노드는레퍼런스를이용하여다음노드를가리키도록만들어노드들을한줄로연결시킴
연결리스트에서는삽입이나삭제시항목들의이동이필요없음 배열 ( 자바, C, C++ 언어 ) 의경우최초에배열의크기를예측하여결정해야하므로대부분의경우배열에빈공간을가지고있으나, 연결리스트는빈공간이존재하지않음 연결리스트에서는항목을탐색하려면항상첫노드부터원하는노드를찾을때까지차례로방문하는순차탐색 (Sequential Search) 을해야
단순연결리스트를위한 SList 클래스
head (a) 새노드삽입전 2 head 2 x 1 (b) 새노드삽입후 [ 그림 2-2] insert_front() 함수
p head (a) 새노드삽입전 p head 2 x 1 2 (b) 새노드삽입후 [ 그림 2-3] insert_after() 함수
head (a) 첫노드삭제전 head 1 x 1 (b) 첫노드삭제후 [ 그림 2-4] delete_front() 함수
p head (a) 노드삭제전 p t head 2 x 1 2 (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 [ 그림 2-8] DList 객체생성 tail
p newnode 4 t 1 2 6 x 6 5 x 5 3 p [ 그림 2-9] insert_before() 의삽입수행
p newnode 4 5 p 2 6 x 6 5 x 3 1 t [ 그림 2-10] insert_after() 의삽입수행
x f 1 4 x 2 r x 3 4 x 3 [ 그림 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() 의노드삽입 last last 3 2 1 newnode
[ 그림 2-15] delete() 의노드삭제 last last 2 2 x 1 x 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 0 1 2 3 top 0 1 2 3 [ 그림 3-3] 리스트로구현된스택
리스트로구현한스택
[ 프로그램 3-1]
단순연결리스트로구현한스택
[ 프로그램 3-2]
수행시간 파이썬의리스트로구현한스택의 push 와 pop 연산은각각 O(1) 시간이소요 파이썬의리스트는크기가동적으로확대또는축소되며, 이러한크기조절은사용자도모르게수행된다. 이러한동적크기조절은스택 ( 리스트 ) 의모든항목들을새리스트로복사해야하기때문에 O(N) 시간이소요 단순연결리스트로구현한스택의 push 와 pop 연산은각각 O(1) 시간 연결리스트의맨앞부분에서노드를삽입하거나삭제하기때문
3.2 스택의응용 컴파일러의괄호짝맞추기 회문 (Palindrome) 검사하기
컴파일러의괄호짝맞추기 [ 핵심아이디어 ] 왼쪽괄호는스택에 push, 오른쪽괄호를읽으면 pop 수행 pop 된왼쪽괄호와바로읽었던오른쪽괄호가다른종류이면에러처리, 같은종류이면다음괄호를읽음 모든괄호를읽은뒤에러가없고스택이 empty 이면, 괄호들이정상적으로사용된것 만일모든괄호를처리한후스택이 empty 가아니면짝이맞지않는괄호가스택에남은것이므로에러처리
[ 예제 1]
[ 예제 2] { ( ) { ( ) ) } { ( ) ( { { { { { { { ( { ( ) { { pty push({) push(() pop() push({) push(() pop() pop()
회문검사하기 회문 (Palindrome): 앞으로부터읽으나뒤로부터읽으나동일한스트링 [ 핵심아이디어 ] 전반부의문자들을스택에 push한후, 후반부의각문자를차례로 pop한문자와비교 회문검사하기는주어진스트링의앞부분반을차례대로읽어스택에 push한후, 문자열의길이가짝수이면뒷부분의문자 1 개를읽을때마다 pop하여읽어들인문자와 pop된문자를비교하는과정을반복수행 만약마지막비교까지두문자가동일하고스택이 empty가되면, 입력문자열은회문
문자열의길이가홀수인경우, 주어진스트링의앞부분 반을차례로읽어스택에 push 한후, 중간문자를읽고 버린다. 이후짝수경우와동일하게비교수행 [ 예제 1] A B S S B A B A A S B A S = S B A B = B A A = A empty push(a) push(b) push(s) pop() pop() pop()
[ 예제 2] R A C E C A R A R R C A R E C A R C =C A R A = A R R = R empty push(r) push(a) push(c) pop() pop() pop()
스택의기타응용 후위표기법 (Postfix Notation) 수식계산하기 중위표기법 (Infix Notation) 수식의후위표기법변환 미로찾기 트리의방문 (4장) 그래프의깊이우선탐색 (8장) 프로그래밍에서매우중요한함수 / 메소드호출및재귀호출도스택자료구조를바탕으로구현
[ 연습문제 ] 수식의표기법 프로그램을작성할때수식에서 +,, *, / 와같은이항연산자는 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 / 8 3 8 2 3 8 3 + 2 = 5 5 1 = 4 1 8 / 4= 5 5 4 8 8 8 2 mpty push(8) push(3) push(2) pop() pop() push(5) push(1) pop() pop() push(4) pop() pop() push(2)
[ 연습문제 ] 중위표기법수식을후위표기법으로변환 [ 핵심아이디어 ] 왼쪽괄호나연산자는스택에 push 하고, 피연산자는출력 입력을좌에서우로문자를 1 개씩읽는다. 읽은문자가 1. 피연산자이면, 읽은문자를출력 2. 왼쪽괄호이면, push 3. 오른쪽괄호이면, 왼쪽괄호가나올때까지 pop 하여출력. 단, 오른쪽이나왼쪽괄호는출력하지않음 4. 연산자이면, 자신의우선순위보다낮은연산자가스택 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 연산, 웹브라우저의방문기록등에사용
스택, 큐, 데크의수행시간비교