6.1 연결된 구조란?
연결된 구조는 흩어진 데이터를 링크로 연결해서 관리한다.
많은 자료를 저장하고 관리하기 위해 배열구조나 연결된 구조를 사용할 수 있다는 것은 공부했다. 배열 구조의 가장 큰 특징은 모든 항목들을 연속된 메모리 공간에 저장하는 것인데, 연결된 구조에서는 이와 같이 데이터를 한군데 모아두는 것을 포기한다.
즉 항목들이 메모리 상 여기저기 흩어져서 존재할 수 있다. 그렇다면 어떻게 모아서 관리할 수 있을까? 링크를 이용한다. 즉 항목들이 다른 항목을 가리키는 하나 이상의 링크(상자에 연결된 줄)을 갖도록 하여 전체 항목들이 하나로 연결되도록 하는 것이다.
이와 같이 항목들을 링크로 연결하여 표현하는 방법을 연결된 구조(Linked structure)라 한다. 특히 항목들을 링크를 통해서 일렬로 나열할 수 있는 연결된 구조를 연결 리스트라 부른다. 그림에서 하나의 상자를 노드(node)라고 하는데, 데이터와 함께 링크를 갖는다. 연결된 구조에서 링크의 수를 늘리면 선형 자료구조 & 이후의 트리, 그래프, 더 복잡한 구조도 효율적으로 표현할 수 있다. 그러나 RAM을 사용하는 배열구조처럼 한번에 k번째 항목의 주소를 계산해서 바로 찾아갈 수 없다.
배열 구조와 연결된 구조의 장단점
- 배열 구조와 달리 연결된 구조는 용량이 고정되지 않는다. 즉 필요한 것만 필요할 때 만들어 쓰기 때문에 메모리를 효율적으로 사용한다. 또한 컴퓨터에 메모리가 남아 있는한 계속 자료를 넣을 수 있다.
- 중간에 자료를 삽입하거나 삭제하는 것이 용이하다. 파이썬의 리스트와 같은 배열 구조에서는 많은 항목의 이동이 필요하다. 그러나 연결된 구조에서는 링크만 수정하면 된다. 그래서 시간 복잡도가 O(1)이다.
- 연결된 구조에서 n번째 항목에 접근하는데 O(n)의 시간이 걸린다. 이것은 배열 구조에 비해서 큰 단점이다. 또한 배열에 비해서 구현이 어렵고 오류가 발생하기도 쉽다.
연결 리스트의 구조
노드(node)
그림의 연결된 구조에서 하나의 상자는 컴퓨터 용어로 노드(node)라고 한다. 배열 구조에서 각 항목들이 데이터만 갖는 것과 달리 노든는 데이터 필드(data field)와 함께 하나 이상의 링크 필드(link field)를 갖는다. 연결 리스트의 대표적인 노드 구조는 다음과 같다.
- 데이터 필드에는 우리가 저장하고 싶은 데이터가 들어간다. 이것은 정수가 될 수도 있고 객체, 다른 리스트도 될 수 있다.
- 링크 필드는 다른 노드를 가리키는, 즉 다른 노드의 주소를 저장하는 변수이다. 이것을 이용해 우리는 다음 노드에 접근할 수 있다.
헤드포인터(head pointer)
연결리스트는 첫 번째 노드만 알면 링크로 매달려 있는 모든 노드에 순차적으로 접근 가능. 그래서 시작 노드의 주소는 반드시 저장해야 한다. (1빠가 누군지 정하는 것처럼) 그리고 연결리스트에서 첫 번째 노드의 주소를 저장하는 변수를 헤드 포인터(head pointer)라 한다. 마지막 노드는 더 이상 갈 곳이 없다. 따라서 링크의 값을 None으로 해서 마지막임을 표시한다.
포인터? 이름은 그냥 짓지 않는다. 다른 객체를 가리키고 있는 변수라는 의미이다. c, c++에서 포인터는 무척 중요. 이들 언어 측면에서 파이썬의 모든 변수는 포인터나 참조자(reference)이다.
연결 리스트의 종류
단순연결리스트(singly linked list)
한 방향으로만의 연결된 구조. 링크는 하나이며 다음 노드의 주소를 기억. 위에서 살펴본 것과 같은 구조가 단순연결리스트.
원형연결리스트
위와 동일해보이지만 마지막 노드 링크 값이 none이 아니라 다시 첫 번째 노드를 가리킨다. 그래서 종료조건에 유의해야 한다.
이중연결리스트(doubly linked list)
하나의 노드가 이전 노드와 다음 노들를 모두 알고 있도록 설계. 그래서 두 개의 링크를 갖는데, 하나는 선행 노드(previous node)를 다른 하나는 후속 노드(next node)를 가리킨다.
선행 노드를 위한 링크가 있으면 어떤 노드에서 이전 노드를 바로 찾아갈 수 있다는 자엄이 있다. 그러나 편리한 만큼 이중으로 링크를 정확하게 유지해야 한다.
6.2 단순연결리스트 응용: 연결된 스택
단순연결리스트로 스택을 구현해보잣! 이런 스택을 연결된 스택(linked stack)라고 한다. 스택은 입출력이 상단으로 제한되는 자료구조. 무엇을 상단으로 사용해야 할까? 헤드 포인터를 스택의 상단으로 사용하면 된다. 모든 자료의 입출력이 top을 통해 가능하므로 추가적인 변수도 필요 없다.
클래스 정의
노드와 스택 클래스를 구현하자. 우선 노드부터, 단순연결리스트를 위한 노든는 데이터 필드와 하나의 링크만 있으면 된다. 이들은 생성자에 선언&초기화 된다. 핵심은 링크의 디폴트 인수는 None
class Node: #노드 클래스
def __init__(self, elem, link = None): # 생성자, 디폴트 인수 사용
self.data = elem #데이터 멤버 생성 및 초기화
self.link = link #링크 생성 및 초기화c++ Java 등과 달리 생성자의 매개변수로 데이터 멤버와 같은 이름을 사용해도 문제가 없다. 클래스의 멤버는 self를 통해 접근하기 때ㅐ문이다. 그래서 link는 매개변수이고 self.link는 데이터 멤버이다.
class LinkedStack:
def __init__(self): #생성자
self.top = None #top 생성 및 초기화
* 데이터 멤버로는 시작 노드를 가리키는 변수 top만 있으면 된다. 아무것도 없으니 첨에는top이 none.
* 스택의 초기화는 스택을 공백상태로 만드는 것. top이 None을 가리키도록
def isEmpty(self): return self.top == None #공백 검사
def clear(self) : return self.top = None #스택 초기화
push(item): 삽입 연산
배열구조와 달리 직접 스택에 넣을 수 없다. 데이터를 넣을 노드를 만들고, 이 노드를 스택의 top에 추가해야 한다. 전체 삽입 구조의 단계는 다음과 같다.
(1) 입력 데이터 E를 이용해 새로운 노드 n을 생성함: n = Node(E)
(2) E의 링크가 시작 노드를 가리키도록 함: n.link = top
(3) top이 n을 가리키도록 함: top = n
실제 구현 코드에서는 Node의 생성자를 이용해 데이터와 링크를 동시에 초기화할 수 있다.
def push (self, item):
n = Node(item, self.top) #1번과 2번
self.top = n #3번 pop():삭제연산
삭제는 상단 항목을 꺼내서 반환하는 연산이다. 연결된 구조에서는 top이 가리키는 노드를 꺼내고 데이터 필드만 반환하면 된다. 이 과정도 살펴보자.
(1) 변수 n이 시작 노드를 가리키도록 함: n = top
(2) top이 다음 노드를 가리키도록 함: top = n.link
(3) 변수 n이 가리키는 노드의 데이터를 반환 return n.data
코드는 아래에 있다. 공백 상태를 반드시 검사해야함! 공백이 아니면 top이 가리키는 노드를 꺼내고 데이터 필드를 반환한다. 노드가 아니라 스택 항목을 반환함에 유의해라.
def pop(self): #삭제연산
if not self.isEmpty(): #공백이 아니면
n = self.top #(1)
self.top = n.link #(2)
return n.data #(3)잠깐, 그럼 데이터는 어떻게 돼? 꺼낸 노드의 메모리는 내가 직접 해제할 필요 없다. 파이썬에서는 객체를 참조하는 변수가 없으면 그 객체는 자동으로 삭제!
peek()
peek은 시작노드의 데이터를 반환하면 된다. 물론 공백상태이면 안 된다.
def peek(self): #연결된 스택의 peek연산
if not self.isEmpty(): #공백이 아니면
return self.top.data #시작노드의 데이터를 반환size()
연결된 구조에서 스택의 항목 수를 구하는 것은 배열구조보다 어렵다. (당연 얘는 len쓰면 끝났다) 마지막 노드는 링크가 None인 노드이다.
시작 노드에서부터 전체 노드를 순회하여 노드를 구할 수 있다. 시장에 가면처럼 0부터 시작해서 None이 나올 때까지 +1을 해서.
def size(self):
node = self.top #시작노드(1빠)
count = 0 #카운트 초기화
while not node == None : #node가 None이 아닐 때까지
node = node.link #다음 노드로 이동
count += 1 #count증가
return count #count 반환 display()
size() 연산에서의 노드 방문방법은 스택 내용을 모두 출력할 때도 동일하게 적용! 모든 노드의 데이터를 출려하려면 모드 노드를 방문해야 하기 때문. 시작부터 마지막 노드까지 방문해보자!
def display(self, msg:'LinkedStack:'): 스택의 항목 출력함수 print(msg, end='') node = self.top while not node == None: print(node.data, end='') node = node.link print()
연결된 스택의 시간 복잡도 분석
연결된 스택의 삽입과 삭제연사의 시간복잡도도 O(1)이다. 그러나 배열 구조에서 파이썬의 리스트가 용량을 증가시켜야 하는 상황이 발생하면 O(n)의 시간이 걸릴 수도 잇는 점을 감안한다면 연결된 스택이 더 유리하다. size는 배열에서는 O(1)이지만 연결된 스택에서는 O(n)이다.
물론 변수 하나 추가하고 삽입 삭제 연산에서 이 변수를 잘 관리하면 상수시간으로 만들 수 있다. you will see this in 과제.
6.3단순연결리스트 응용: 연결된 리스트
스택과 달리 리스트는 항목의 삽입이나 삭제가 시작노드 뿐만 아니라 임의의 위치에서도 가능하다. 리스트 ADT를 구현하기 위해 더 복잡한 연결구조를 쓸 수도 있지만 단순 연결리스트를 우선 사용재보자.
클래스의 정의
노드는 연결된 스택에서와 완전히 동일하므로 같은 코드를 사용한다. 연결된 리스트의 이름은 LinkedList. 데이터 멤버는 헤드 포인터인 head만으로 충분. 공백도 스택과 동일하다
class LinkedList: def__init__(self): self.head = None def isEmpty(self):return self.head == None def clear(self): self.head == None def size( self ): node = self.head #시작노드(1빠) count = 0 #카운트 초기화 while not node == None : #node가 None이 아닐 때까지 node = node.link #다음 노드로 이동 count += 1 #count증가 return count #count 반환 def display(self, msg): 요것 역시 위의 코드에서 head와 형식만 조금 다르게
getNode(pos): 새로운 연산 추가
리스트 ADT에 없는 연산을 추가하자. pos번째 노드를 반환하는 연산이다. 연결된 구조에서는 노드를 사용하기에 pos번째 노드를 반환하는 getNode(pos)가 필요하다. 이는 역시 head부터 시작해서 링크를 따라 순차적으로 찾아가서 해당 노드를 반환하면 된다. get노드 역시 시간 복잡도는 O(n). pos번 움직여야 원하는 노드에 접근가능.
def getNode(self,pos): if pos < 0 : return None node = self.head #노드는 head부터 시작 while pos > 0 and node != None: node = node.link pos -= 1 #위치를 줄이지 않으면 loop가 끝나지 않는다 return node
getEntry(pos), replace(pos, elem), find(val)
getNode 연산이 구현되면 항목의 데이터만을 반환하는 getEntry를 다음과 같이 간단히 구현할 수 있다.
def getEntry(self, pos): node = self. getNode(pos) #pos번째 노드 if node == None : return None #찾는 노드가 없는 경우 else : return node.data #그 노드의 데이터 필드를 반환이 연산의 시간 복잡도는? 배열로 했을 때는 O(1)이었다. 연결된 리스트에서는 getNode가 O(n)이므로 이 연산도 O(n)이 된다. 이는 배열에 비해서 매우 비효율적이지만 메모리가 흩어져 있어서 어쩔 수 없다.
어떤 위치의 항목을 다른 데이터로 변경하는 replace연산은 getNode를 통해서 간단히 구현할 수 있다.def replace(self, pos, elem) : node = self.getNode(pos) #pos번째 노드를 찾아 if node != None:node.data = elem #데이터필드에 elem 복사하나씩 하는 데이터를 가진 노드를 찾는 함수도 비교적 간단하다. head부터 연결된 노드를 하나씩 방문하면서 검사하면 되기 때문이다.
def find(self, data): #데이터로 data를 갖는 노드 반환 node = self.head; while node is not None: #모든 노드에서 찾음 if node.data == data : return node #찾으면 바로 반환 node = node.link return node #찾지 못하면 None을 반환
insert(pos, elem) : 삽입 연산
다음의 단순연결리스트에서 임의의 위치에 노드를 삽입하는 과정을 보여준다. 삽입결과를 보면 pos위치의 노드가 아니라 그 이전노드 before 링크 값이 수정되는 것에 유의하라. 즉, pos 위치에 새로운 노드를 삽입하려면 그 노드의 선행 노드를 알아야 한다.
(1) 노드 N이 노드 C를 가리키게 함: node.link = before.link
(2) 노드 B가 노드 E를 가리키게 함: before.link = node
이 연산의 시간 복잡도는 어떻게 될까? 만약 before를 알고 있다면 두 단계만에 처리되고, 따라서 O(1)이다. 배열 구조를 이용한 경우는 위치를 알더라도 항목의 이동을 위해 O(n)이 필요한 것을 기억. 이것이 연결리스트의 장점.
만약 before를 모르고 삽입할 위치의 노드만 알고 있다면 어떻게 될까? 단순연결리스트의 노드에 선행노드에 대한 정보가 없다. 따라서 시작노드부터 하나씩 검사해야 한다. 이것은 before를 찾기 위해 O(n)의 시간이 필요한 것을 의미한다. 삽입연산에서 맨 앞에 노드를 삽입하는 경우는 멤베변수인 head가 변경되어야 하므로 다음 코드와 같이 특별하게 처리해줘야 한다.
def insert(self, pos, elem):
before = self.getNode(pos-1) #before 노드를 찾음
if before == None: #맨앞에 삽입하는 경우
self.head == Node(elem, self.head) #맨 앞에 삽입함
else : #중간에 앞에 삽입하는 경우
node = Node(elem, before.link) #노드 생성 + step1
before.link = node #step2 before를 찾는 getNode(pos-1)에 유의. before는 pos-1번째 노드다. 이 연산의 시간복잡도는? 실제 삭제 과정은 O(1)이지만 before 찾기 위해 O(n)이 걸린다. 따라서 전체 시간 복잡도는 O(n)으로 배열에서와 동일하다. 그러나 만약 before을 알고 있다면 삽입은 O(1)만에 처리된다.
delete(pos): 삭제 연산
삭제에서도 삭제할 pos위치의 노드가 아니라 before노드가 필요하다. 만약 before를 알고 있다면 삭제 연산은 다음과 같이 간단히 처리된다.
- before의 link가 삭제할 노드의 다음 노드를 가리키도록 함
before.link = before.link.link
이 연산의 시간복잡도도 만약 before을 알고 있다면 한 단계만에 처리되므로 O(1)이다. 배열에서는 삭제할 위치를 알더라도 항목들의 이동을 위해 O(n)이 필요했다. 삽입에서와 같이 before을 모르고 삭제할 노드만 알고 있다면 before를 찾기 위해 O(n)이 필요하다. 삭제 연산 코드는 다음과 같다. insert와 마찬가지로 시작노드를 삭제하는 경우는 head가 바뀌게 되므로 특별하게 처리해줘야한다.
def delete(self, pos):
before = self.getNode(pos-1) #before 노드를 찾음
if before == None : # 시작 노드를 삭제
if self.head is not None: #공백 아니면
self.head = self.head.link #head를 다음으로 이동
elif before.link != None: #중간에 있는 노드 삭제
before.link = before.link.link #step1이 연산 역시 getNode(pos-1)로 before를 찾기 위해 O(n)이 소요된다. ADT연산들 중에서 sort와 merge는 제외한다. 정렬을 직접 구현하는 것은 약간 복잡.
6.4 원형연결리스트의 응용:연결된 큐
큐도 연결된 구조로 구현할 수 있는데, 이러한 큐를 연결된 큐(linked queue)라고 한다. 연결된 큐도 크기가 제한되지 않고 필요한 메모리만 사용한다는 장점과, 코드가 더 복잡하고 링크 필드 때문에 메모리 공간을 더 사용하는 단점.
연결된 큐를 구현하는 가장 간단한 방법은 다음과 같이 단순 연결리스트를 사용하는 것으로. 맨 앞과 뒤에 있는 노드를 front와 rear가 가리키는 구조이다. 물론 삽입은 후단(rear), 삭제는 전단(front)에서 이루어져야 한다.
약간 더 복잡한 구조를 생각할 수 있다. 다음과 같이 마지막 노드의 링크가 첫 노들르 가리키는 원형연결리스트를 이용하는 것이다.
rear == tail // front == tail.link
이 구조에서는 tail(또는 rear)만을 변수로 저장한다. front는 어떻게 알 수 있을까? tail의 다음 노드, 즉 tail.link 가 front이다.
만약 tail이 아니라 head(또는 front)만을 사용하면 어떻게 될까? 이 경우 front는 바로 접근이 가능하다. 그런데 rear도 바로 찾아갈 수 있을까? 불가능하다. 링크를 따라 후속노드 전체를 끝까지 이동해야 드디어 rear에 도착한다. 따라서 tail을 사용하는 것이 rear과 front에 바로 접근할 수 있다는 점에서 훨씬 효율적이다.
원결된 큐를 원형연결리스트로 구현할 때 필요한 멤버 변수는 tail 뿐이다. 후단은 rear == tail이고. 삭제를 위한 전단은 front == tail.link이므로 모두 O(1)만에 접근할 수 있다. 큐의 동작은 스택보다 약간 더 복잡하다.
클래스 정의
노드 클래스는 앞에서 공부한 스택이나 리스트에서와 동일. 원형연결리스트로 구현한 큐 클래스를 CircularLinkedQueue라 하자. 공백검사와 초기화, peek 등의 연산은 다음과 같이 매우 간단하다. peek은 큐가 공백이 아닐 경우 front(tail.link)의 data를 반환하면 된다.
class CircularLinkedQueue:
def __init__(self): #생성자 함수
self.tail = None #tail:유일한 데이터
def isEmpty(self) : return self.tail == None #공백검사
def clear(self) : self.tail = None #큐 초기화
def peek(self):
if not self.isEmpty():
return self.tail.link.data #front의 data 반환enqueue(): 삽입 연산
항목의 삽입은 후단을 통해 이루어진다. 삽입은 큐가 공백상태인 경우와 그렇지 않은 경우가 약간 다르다. 공백상태가 더 쉽다. 다음은 공백상태의 큐에 항목을 삽입하는 과정을 보여준다.
(1) 입력 데이터 E를 이용해 새로운 노드 n을 생성함 : n = Node(E,NOne)
(2) n의 링크가 자신을 가리키도록 함 : n.link = n
(3) tail이 n을 가리키도록 함 : tail = n
만약 공백상태가 아니면 다음과 같이 약간 더 복잡해진다.
(1) 입력 데이터 E를 이용해 새로운 노드 n을 생성함 : n = Node(E, None)
(2) n의 링크가 front를 가리키도록 함: n.link = tail.link
(3) tail의 링크가 n을 가리키도록 함 : tail.link = n
(4) tail이 n을 가리키도록 함 : tail = n
def enqueue(self, item):
node = Node(item,None)
if self.isEmpty():
node.link = node
self.tail = node
else:
node.link = self.tail.link
self.tail.link = node
self.tail = node
dequeue():삭제연산
삭제연산은 front(또는 tail.link)를 연결구조에서 꺼내고 데이터 필드를 반환하는 것이다. 큐는 반드시 공백이 아니어야 삭제가 가능하다. 큐가 항목을 하나만 가지고 있는 경우는 삭제하고 나면 공백 상태가 되므로 일반적인 경우와 분리해서 처리해야 한다.
(1) n이 전단노드(front)를 가리키도록 함: n = tail.link
(2) tail이 None을 가리키도록 함: tail = None
(3) n이 가리키는 노드의 데이터를 반환함 : return n.data
큐가 두 개 이상의 항목을 갖는 경우의 삭제는 다음과 같다.
(1) n이 전단노드(front)를 가리키도록 함: n = tail.link
(2) tail의 링크가 front의 링크를 가리키도록 함: tail.link = n.link
(3) n이 가리키는 노드의 데이터를 반환함 : return n.data
def dequeue(self):
if not self.isEmpty():
data = self.tail.link.data
if self.tail.link == self.tail: #항목이 하나
self.tail = None
else:
self.tail.link = self.tail.link.link
return data size(), print()
큐의 크기를 구하거나 큐의 내용을 출력하기 위해서 tail부터 노드를 따라가면서 한 바퀴 돌아와야 한다. size 연산을 위한 순회 방법은 그림과 같다.
def size(self):
if self.isEmpty() : return 0 #공백 0 반환
else:
count = 1
node = self.tail.link
while not node == self.tail:
node = node link
count += 1
return count #최종 count 반환 display()
이러한 방문 방법은 display연산에서도 적용된다. 코드는 다음과 같다. 종료조건에 주의하자!
def display(self, msg = 'CircularLinkedQueue:'):
print(msg, end='')
if not self.isEmpty():
node = self.tail.link
while not node == self.tail :
print(node.data, end='')
node = node.link
print(node.data, end='')
print()원형큐에서는 용량이 제한되었는데, 연결된 큐에서는 이런 문제가 전혀 없다. 시간 복잡도는 삽입과 삭제가 모두 O(1)로 원형큐와 차이가 없다.
6.5 이중연결리스트의 응용: 연결된 덱
연결된 구조로 덱을 구현해보자. 이러한 덱을 연결된 덱(linked dequeue)라고 하다. 먼저 덱을 단순연결리스트로도 구현할 수 있다. 그림과 같이 전단과 후단을 각각 front와 rear가 가리키고, 양쪽에서 삽입과 삭제가 가능한 구조이다.
이 구조는 deleteRear연산에서 문제가 발생. 다른 연산들은 모두 O(1)에 처리가 가능한데 비해 이 연산은 O(n)이 걸린다. 왜 그럴까? 후단을 삭제하고 나면 rear가 한 칸 앞으로 움직여야 한다. 그런데 단순연결리스트의 노드에는 선행노드의 정보가 없다. 따라서 front부터 시작하여 선행노드를 찾기 위해 전체 노드를 탐색해야 한다. 이 과정은 O(n)이 소요된다.
이 문제를 해결하는 방법은 이중연결리스트를 사용하는 것이다. 다음 그림과 같이 모든 노드가 선행노드와 후속노드를 알고 있다면 deleteRear도 O(1)에 처리가 가능하다. 따라서 연결된 덱은 반드시 이중연결리스트로 구현하는 것이 좋다.
클래스 정의
이중연결리스트를 위한 노드는 두 개의 링크를 갖는다. 이들을 각각 prev, next라 하자. 노드 클래스의 이름은 DNode로 하고, 생성자에 디폴트 인자를 적용한 구현 예는 다음과 같다.
class DNode
def __init__(self, elem, prev = None, next = None):
self.data = data
self.prev = prev
self.next = netx연결된 덱 클래스를 DoublyLinkedDeque라 하자. 전단과 후단을 위해 front와 rear를 데이터 갖는다. 공백 상태는 전단이나 후단이 None인 경우. 전단을 기준으로 하자. self.front == None이면 공백상태. 초기화는 양단을 모두 None으로 처리하면 확실
class DoublyLinkedDeque:
def __init__(self):
self.front = None
self.rear = None
def isEmpty(self): return self.front == None
def clear(self): self.front = self.front = None이중 연결리스트를 사용하더라도 size나 display의 연산은 단순연결리스트에서의 동작과 차이가 없다. 연결된 스택의 코드를 대부분 이용. getFront와 getRear연산도 front와 rear가 가리키는 노드의 데이터를 반환하면 된다. 여기서는 삽입과 삭제 연산만!
addFront():전단 삽입
전단을 통한 삽입을 먼저 알아보자. 과정은 다음과 같다.
(1) 노드 생성 및 prev, next초기화: n = DNode(item, None, front)
(2) front가 선행노드로 n을 가리킴: front.prev = n
(3) 이제 front가 n을 가리킴: front = n
첫번째 단계에서 노드의 생성자를 이용해 링크를 초기화한다. 전단에 삽입(addFront)되는 노드의 경우 prev는 None. next는 현재의 전단, 즉 front가 되어야 한다. 만약 공백이라면 front와 rear가 n을 가리키도록.
def addFront(self, item):
node = DNode(item, None,self.front)
if(self.isEmpty()):
self.front = self.rear = node
else:
self.front.prev = node
self.front = nodeaddRear():후단산입
후단 산입도 유사. 이제 n의 next가 None. prev의 후단인 rear이 되어야. 다음으로 rear가 새로운 노드를 가리키면 된다. 전후단 삽입의 시간 복잡도는 모두 O(1)
def addRear(self, item):
node = DNode(item, self.rear, None)
if(self.isEmpty()):
self.front = self.rear = node
else:
self.rear.prev = node
self.rear = nodedeleteFront(), deleteRear():전후단 삭제
전단 삭제를 알아보자.
(1) 삭제할 노드(front)의 데이터 복사: data = front.data
(2) front를 다음으로 옮김 : front = front.next
(3) front를 이전노드는 None: front.prev = None
(4) 데이터를 반환 : return data
만약 노드가 하나뿐이라면 rear도 None으로 설정해야 함에 유의하라. 후단 삭제 deleteRear도 거의 비슷하게 처리된다. 이들 연산은 다음 코드로 구현된다.
def deleteFront(self):
if not self.isEmpty():
data = self.front.data
self.front = self.front.next
if self.front == None:
self.rear == None
else:
self.front.prev = None
return data
def deleteRear(self):
if not self.isEmpty():
data = self.rear.data
self.rear = self.rear.prev
if self.rear == None:
self.front == None
else:
self.rear.next = None
return data
전후단 삭제의 시간복잡도는 모두 O(1)이다 만약 단순연결리스트라면 deleteRear은 O(n).
