리스트를 할당할 주소값과 리스트의 크기를 전달받아 리스트를 생성하고, 생성된 리스트의 주소값을 반환한다.
일반 메서드
boolean isEmpty()
리스트에 원소가 하나도 없는지 확인
리스트에 원소가 하나도 없을 경우 True(1), 하나라도 있을 경우 False(0)을 반환한다.
integer size()
리스트에 저장되어 있는 원소 개수를 반환한다.
void traverse()
리스트의 원소를 순회한다
접근 메서드
element get(r)
랭크를 입력받아 해당 랭크의 원소를 반환한다.
갱신 메서드
element set (r, e)
랭크와 원소를 입력받아 해당 랭크에 원소를 저장
void add(r,e)
랭크와 원소를 입력받아 해당 랭크에 원소를 추가
void addFirst(e)
원소를 입력받아 리스트 첫번째 랭크에 원소를 추가
void addLast(e)
원소를 입력받아 리스트 마지막 랭크에 원소를 추가
element remove(r)
원소를 입력받아 리스트에서 해당 원소 삭제
element removeFirst()
리스트 첫번째 원소 삭제
element removeLast()
리스트 마지막 원소 삭제
예외 상황 (throw exception)
invalidRankException()
해당 랭크가 리스트에 존재하지 않을때
fullListException()
이미 꽉 찬 리스트에 원소를 추가하려고 할 때
emptyListException()
이미 비어있는 리스트에서 원소를 삭제하려고 할 때
배열을 이용한 리스트
V[0..N] 을 이용해 리스트를 구현한다
순위는 0부터 시작한다
get(r), set(r,e)이 O(1) 시간에 V[r]을 반환/저장하도록 구현
r<0 또는 r>n-1인 경우 처리할 invalidRankException() 구현한다
초기화 메서드
array * initialize(array * parr, int N)
Alg initialize()
// input : array V, integer N, integer n
// output : array V (size N)
n <- 0
return V
일반 메서드
boolean isEmpty()
Alg isEmpty()
// input array V, integer N, integer n
// output boolean
if (n=0)
return true
else
return false
integer size()
Alg size()
// input array V, integer N, integer n
// output integer n
return n
void traverse()
Alg traverse()
// input array V, integer N, integer n
// output None
for r <- 0 to n-1
visit(V[r])
return
접근 메서드
element get(r)
Alg get(r)
// input array, integer N, integer n, rank r
// output element
if ((r<0) || (r>n))
invalidRankException()
if (n=0)
emptyListException()
return V[r]
갱신 메서드
element set (r, e)
Alg set(r,e)
// input array, integer N, integer n, rank r, element e
// output none
if ((r<0) || (r>n))
invalidRankException()
V[r] <- e
return e
void add(r,e)
배열 구현에서는 r 순위로 새 원소가 들어갈 빈 자리를 만들기 위해 V[n-1] ~ V[r] 까지배열 뒤쪽으로 밀어야 한다.
Alg add(r, e)
// input array V, integer N, integer n, rank r, element e
// output none
if (n=N)
fullListException()
if ((r<0) || (r>n))
invalidRankException()
for i <- n-1 downto r
V[i+1] <- V[i]
V[r] <- e
n <- n+1
return
[그림 1] 배열 리스트의 삽입과정
void addFirst(e)
원소를 입력받아 리스트 첫번째 랭크에 원소를 추가
Alg addFirst(e)
// input array V, integer N, integer n, element e
// output none
if (n=N)
fullListException()
for i <- n-1 downto 0
V[i+1] <- V[i]
V[0] <- e
n <- n+1
return
void addLast(e)
원소를 입력받아 리스트 마지막 랭크에 원소를 추가
Alg addLast(e)
// input array V, integer N, integer n, element e
// output none
if (n=N)
fullListException()
n <- n+1
V[n-1] <- e
return
element remove(r)
원소를 입력받아 리스트에서 해당 원소 삭제
r 순위에서 삭제된 원소 자리를 채우기 위해 V[r+1] .. V[n-1] 원소를배열앞으로 땡겨온다.
Alg remove(r)
// input array V, integer N, integer n, rank r
// output element e
if ((r<0) || (r>n-1))
invalidRankException()
if (n=0)
emptyListException()
e <- V[r]
for i <- r+1 to n-1
V[i-1] <- V[i]
n <- n-1
return e
[그림 2] 배열 리스트의 삭제 과정
element removeFirst()
리스트 첫번째 원소 삭제
Alg removeFirst()
// input array V, integer N, integer n
// output element e
if (n=0)
emptyListException()
e <- V[0]
for i <- 1 to n-1
V[i-1] <- V[i]
n <- n-1
return e
element removeLast()
리스트 마지막 원소 삭제
Alg removeLast()
// input array V, integer N, integer n
// output element e
if (n=0)
emptyListException()
e <- V[n-1]
n <- n-1
return e
# array_linked_list.py
from asyncio.windows_events import NULL
class linked_list:
# 초기 n=0 (원소 개수)
def __init__(self):
self.n = 0
# 리스트 초기화 메서드
def initialize(self, N):
self.arr = [0]*N
self.N = N
# 일반 메서드
def isEmpty(self):
if self.n == 0:
return True
else:
return False
def size(self):
return self.n
def traverse(self):
for i in range(self.n):
print(self.arr[i], end=' ')
print()
return
# 접근 메서드
def get(self, r):
if r<0 or r>self.n:
print("invalidRankException")
return NULL
elif self.n == 0:
print("emptyListException")
return NULL
else:
return self.arr[r]
# 갱신 메서드
def set(self, r, e):
if r<0 or r>self.n:
print("invalidRankException")
return NULL
else:
self.arr[r] = e
return e
def add(self, r, e):
if self.n == self.N:
print("fullListException")
elif r<0 or r>self.n:
print("invalidRankException")
else:
for i in range(self.n-1, r, -1):
self.arr[i+1] = self.arr[i]
# 기존에 있던 원소를 replace할 경우 n 증가 X, 원소가 새로 추가된 경우 n 증가
if self.arr[r] == 0:
self.n += 1
self.arr[r] = e
return
def addFirst(self, e):
if self.n == self.N:
print("fullListException")
elif self.n > 0:
for i in range(self.n-1, -1, -1):
self.arr[i+1] = self.arr[i]
self.arr[0] = e
self.n += 1
return
def addLast(self, e):
if self.n == self.N:
print("fullListException")
else:
self.n += 1
self.arr[self.n - 1] = e
return
def remove(self, r):
if r<0 or r>self.n-1:
print("invalidRankException")
return NULL
elif self.n == 0:
print("emptyListException")
return NULL
else:
e = self.arr[r]
for i in range(r+1, self.n):
self.arr[i-1] = self.arr[i]
self.n -= 1
return e
def removeFirst(self):
if self.n == 0:
print("emptyListException")
return NULL
else:
e = self.arr[0]
for i in range(1, self.n):
self.arr[i-1] = self.arr[i]
self.n -= 1
return e
def removeLast(self):
if self.n == 0:
print("emptyListException")
return NULL
else:
e = self.arr[self.n-1]
self.n -= 1
return e
from array_linked_list import linked_list
# 클래스 호출
new_list = linked_list()
# 리스트 초기화
new_list.initialize(5) # 길이 5인 배열 리스트 생성
new_list.addFirst(1) # 리스트 첫번째 (인덱스 0)에 원소 1 추가
new_list.traverse() # 리스트 순회 및 출력
new_list.addLast(3) # 리스트 마지막 (인덱스 1)에 원소 3 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.add(1, 2) # 리스트 두번째에 (인덱스 1)에 원소 2 추가
new_list.addLast(4) # 리스트 마지막 (인덱스 2)에 원소 4 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
print(new_list.isEmpty()) # 리스트 비어있지 않으므로 False 출력
new_list.addFirst(7) # 리스트 첫 번째에 원소 7 추가
new_list.addFirst(6) # 리스트 첫 번째에 원소 6 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
print(new_list.size()) # 리스트 사이즈 출력 (5)
new_list.addLast(8) # 오류 상황 발생. fullListException
print('#'*10)
new_list.add(7, 10) # 리스트 여덟번째 (인덱스 7)에 원소 10 추가 -> 배열 길이 초과하므로 오류 발생
print('#'*10)
new_list.remove(3) # 리스트 네번째 삭제 (원소 2)
new_list.traverse() # 리스트 순회 및 출력
new_list.removeLast() # 리스트 마지막 삭제 (원소 4)
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.removeFirst() # 리스트 첫번째 삭제 (원소 6)
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.remove(1) # 리스트 두 번째 삭제(인덱스 1, 원소 1)
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.removeFirst()
print(new_list.isEmpty()) # 리스트 비어있으므로 True 출력
new_list.removeLast() # 원소 존재하지 않는 상태에서 삭제, 오류 발생
단일연결리스트 (singly linked list) : 연속 노드로 구성된 데이터 구조 <단방향 순회만 가능>
이중연결리스트 (doubly linked list) : 연속 노드로 구성된 데이터 구조 <양방향 순회 가능>
[그림 4] 단일연결리스트 vs 이중연결리스트
초기화 메서드
array * initialize(array * parr, int N)
초기에는 아무 노드도 없다 -> O(1) 시간 소요
Alg initialize()
// input : none
// output : an empty doubly linked list with header H and trailer T
H <- getnode()
T <- getnode()
H.next <- T
T.prev <- H
n <- 0
return
일반 메서드
boolean isEmpty()
Alg isEmpty()
// input array V, integer N, integer n
// output boolean
if (n=0)
return true
else
return false
integer size()
Alg size()
// input array V, integer N, integer n
// output integer n
return n
void traverse()
연결리스트의 모든 원소들을 방문 -> O(n) 시간 소요
Alg traverse()
// input : a doubly linked list with header H and trailer T
// output : none
p <- H.next
while (p!=T)
visit(p.elem)
p <- p.next
return
접근 메서드
element get(r)
Alg get(rank r)
// input : a doubly linked list with header H and trailer T, rank r
// output : element
if ((r<1) || (r>n))
invalidRankException()
p <- H
for i <- 1 to r
p <- p.next
return p.elem
갱신 메서드
element set (r, e)
Alg set(rank r, element e)
// input : a doubly linked list with header H and trailer T, rank r, element e
// output : element
if ((r<1) || (r>n))
invalidRankException()
p <- H
for i <- 1 to r
p <- p.next
p.elem <- e
return e
void add(r,e)
새 노드를 할당해서 이전, 이후 노드와 연결한다
Alg add(r,e)
# input : a doubly linked list with header H and trailer T, rank r, node p, element e
# output : none
if ((r<1) || (r>n))
invalidRankException()
p <- H
# 의도한 rank까지 이동하고 addNodeBefore 함수 호출
for i <- 1 to r
p <- p.next
# 새 노드 할당하고 연결
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
n <- n+1
return
[그림 5] 연결리스트 삽입 과정
void addFirst(e)
원소를 입력받아 리스트 첫번째 랭크에 원소를 추가
Alg addFirst(e)
# input : a doubly linked list with header H and trailer T, element e
# output : none
p = self.head.next
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
self.n += 1
return
void addLast(e)
원소를 입력받아 리스트 마지막 랭크에 원소를 추가
Alg addLast(e):
# input : a doubly linked list with header H and trailer T, element e
# output : none
p = self.tail.prev
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
self.n += 1
return
element remove(r)
Alg remove(r)
// input : a doubly linked list with header H and trailer T, node p, rank r
// output : element
if ((r<1) || (r>n))
invalidRankException()
p <- H
for i <- 1 to r
p <- p.next
# 노드 삭제
e <- p.elem
(p.prev).next <- p.next
(p.next).prev <- p.prev
n <- n-1
return e
Alg removeNode(p)
// input : a doubly linked list with header H and trailer T, node p, rank r
// output : element
e <- p.elem
(p.prev).next <- p.next
(p.next).prev <- p.prev
putnode(p)
return e
[그림 6] 연결리스트 삭제 과정
element removeFirst()
리스트 첫번째 원소 삭제
Alg removeFirst()
// input : a doubly linked list with header H and trailer T, rank r, int n
// output : element
if (n=0)
emptyListException()
e <- removeNode(H.next)
n <- n-1
return e
element removeLast()
리스트 마지막 원소 삭제
Alg removeLast()
// input : a doubly linked list with header H and trailer T, rank r, int n
// output : element
if ((r<0) || (r>n-1))
invalidRankException()
if (n=0)
emptyListException()
e <- removeNode(T.prev)
n <- n-1
return e
# singly_linked_list.py
from asyncio.windows_events import NULL
class node():
def __init__(self, data, next=NULL):
self.data = data
self.next = next
class singly_linked_list():
# 동적 할당 받으면 되니까 처음부터 공간 얼마 필요한지 필요 X
def __init__(self):
self.head = node(NULL)
self.n = 0
# 일반 메서드
def isEmpty(self):
if self.n == 0:
return True
else:
return False
def size(self):
return self.n
def traverse(self):
p = self.head
while p != NULL:
print(p.data, end=' ')
p = p.next
print()
return
# 접근 메서드
def get(self, r):
if r<1 or r>self.n:
print("invalidRankException")
return NULL
else:
p = self.head
for i in range(1, r+1):
p = p.next
return p.data
# 갱신 메서드
def set(self, r, e):
if r<1 or r>self.n:
print("invalidRankException")
return NULL
else:
p = self.head
for i in range(1, r+1):
p = p.next
p.data = e
return e
def addFirst(self, e):
p = self.head
q = node(e, p.next)
p.next = q
self.n += 1
return
def removeFirst(self):
if self.n == 0:
print("emptyListException")
return NULL
else:
p = self.head
e = p.data
p.next = (p.next).next
self.n -= 1
return e
# doubly_linked_list.py
from asyncio.windows_events import NULL
class node():
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
class doubly_linked_list():
# 동적 할당 받으면 되니까 처음부터 공간 얼마 필요한지 필요 X
def __init__(self):
self.head = node(NULL)
self.tail = node(NULL)
# tail prev에 head 할당
self.head.next = self.tail
self.tail.prev = self.head
self.n = 0
# 일반 메서드
def isEmpty(self):
if self.n == 0:
return True
else:
return False
def size(self):
return self.n
def traverse(self):
p = self.head.next # 첫 노드
while p != self.tail:
print(p.data, end=' ')
p = p.next
print()
return
# 접근 메서드
def get(self, r):
if r<1 or r>self.n:
print("invalidRankException")
return NULL
else:
p = self.head
for i in range(1, r+1):
p = p.next
return p.data
# 갱신 메서드
def set(self, r, e):
if r<1 or r>self.n:
print("invalidRankException")
return NULL
else:
p = self.head
for i in range(1, r+1):
p = p.next
p.data = e
return e
def addNodeBefore(p, e):
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
return
def add(self, r, e):
if r<1 or r>self.n:
print("invalidRankException")
else:
p = self.head
for i in range(1, r+1):
p = p.next
# i -1 에 값 존재할 경우 -> 값 갱신
if p.next.data != NULL:
p.next.data = e
else:
# 존재하지 않을 경우 새 노드 할당
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
self.n += 1
return
def addFirst(self, e):
p = self.head.next
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
self.n += 1
return
def addLast(self, e):
p = self.tail
q = node(e, p.prev, p)
p.prev.next = q
p.prev = q
self.n += 1
return
def remove(self, r):
if r<1 or r>self.n:
print("invalidRankException")
return NULL
p = self.head
for i in range(1, r+2):
p = p.next
# 노드 삭제
e = p.data
p.prev.next = p.next
p.next.prev = p.prev
self.n -= 1
return e
def removeFirst(self):
if self.n == 0:
print("emptyListException")
return NULL
else:
p = self.head.next
e = p.data
p.prev.next = p.next
p.next.prev = p.prev
self.n -= 1
return e
def removeLast(self):
if self.n == 0:
print("emptyListException")
return NULL
else:
p = self.tail.prev
e = p.data
p.prev.next = p.next
p.next.prev = p.prev
self.n -= 1
return e
이전 예제와 동일하게 실행하되, 동적할당이므로 fullListException 예외처리는 제외했다 (물론 최대 크기를 지정해준다면 발생 가능하다)
from doubly_linked_list import doubly_linked_list
# 클래스 호출
new_list = doubly_linked_list()
# 리스트 초기화
#new_list.initialize(5) # 길이 5인 배열 리스트 생성
new_list.addFirst(1) # 리스트 첫번째 (인덱스 0)에 원소 1 추가
new_list.traverse() # 리스트 순회 및 출력
new_list.addLast(3) # 리스트 마지막 (인덱스 1)에 원소 3 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.add(1, 2) # 리스트 두번째에 (인덱스 1)에 원소 2 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.addLast(4) # 리스트 마지막 (인덱스 2)에 원소 4 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
print(new_list.isEmpty()) # 리스트 비어있지 않으므로 False 출력
print('#'*10)
new_list.addFirst(7) # 리스트 첫 번째에 원소 7 추가
new_list.addFirst(6) # 리스트 첫 번째에 원소 6 추가
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
print(new_list.size()) # 리스트 사이즈 출력 (5)
# new_list.addLast(8) # 오류 상황 발생. fullListException
# print('#'*10)
new_list.add(7, 10) # 리스트 여덟번째 (인덱스 7)에 원소 10 추가 -> 배열 길이 초과하므로 오류 발생
print('#'*10)
new_list.remove(3) # 리스트 네번째 삭제 (원소 2)
new_list.traverse() # 리스트 순회 및 출력
new_list.removeLast() # 리스트 마지막 삭제 (원소 4)
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.removeFirst() # 리스트 첫번째 삭제 (원소 6)
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.remove(1) # 리스트 두 번째 삭제(인덱스 1, 원소 1)
new_list.traverse() # 리스트 순회 및 출력
print('#'*10)
new_list.removeFirst()
print(new_list.isEmpty()) # 리스트 비어있으므로 True 출력
new_list.removeLast() # 원소 존재하지 않는 상태에서 삭제, 오류 발생
<실행 결과>
[그림 7] 실행 결과
이전과 동일한 실행 결과를 확인할 수 있다
구현 방법에 따른 성능 비교
작업
배열
연결리스트
size, isEmpty
1
1
get, set
1
n
add, remove
n
n
addFirst, removeFirst
n
1
addLast, removeLast
1
1
get, set 메서드에서는 배열이, addFirst, removeFirst 메서드에서는 연결리스트 구현방식이 유리함을 알 수 있다.
