자료구조 및 실습 - [4] 리스트 (1)

리스트 ADT

먼저 ADT에 대해 알아보자.

ADT (추상자료형, Abstract data type) : 데이터 구조의 추상형 

이라고 정의하며 ADT는 다음을 나타낸다.

- 저장된 데이터
- 데이터에 대한 작업들
- 작업 중 발생 가능한 에러 상황들

이것을 리스트로 표현하면 리스트 ADT가 되는 것이다. 사실 말이 조금 어렵긴 한데 연속적인 임의 개체들을 모델링한 것이라고 볼 수 있다. 리스트의 원소에 대한 접근 도구로는 순위(rank)가 있다. 

---

리스트 ADT 메서드

리스트 ADT에서 원소는 순위 (rank), 즉 그 원소 앞의 원소 개수를 특정하여 접근, 삽입, 또는 삭제한다. 말로는 어렵지만 그림을 그려보면 더욱 이해가 쉬울 것이다.

리스트 ADT 메서드
- 일반 메서드
  boolean isEmpty() #리스트가 비었는지 확인
  integer size() #리스트의 사이즈 반환
  iterator elements() #모든 리스트 원소 출력

- 접근 메서드
  element get(rank) # 해당 rank에 있는 원소 반환

- 갱신 메서드
  element set(rank, element) # 해당 rank의 원소를 set
  add(rank, element) # 해당 rank에 새로운 노드를 추가
  addFirst(element) # rank 1에 새로운 노드 추가
  addLast(element) # rank Last에 새로운 노드 추가
  element remove(rank) #해당 rank에 있는 노드 제거
  element removeFirst() # rank 1에 새로운 노드 제거
  element removeLast() # rank Last에 새로운 노드 제거

 

리스트 ADT를 구성하면서 예외를 구성해줘야 한다. 여기서 예외란 어떤 ADT작업을 실행하고자 할 때 발생할 수도 있는 오류 상황을 뜻한다. 예를 들어 rank에 음수가 입력되는 상황이 있다. 리스트 ADT에서 발령 가능한 예외는 다음과 같다.

invalidRankException() # 유효하지 않은 rank
fullListException() # 리스트가 꽉 차있을 때
emptyListException() # 리스트가 비었는데 get or remove 등..

 

리스트 ADT는 배열과 연결리스트를 활용하여 구현할 수 있다.

---

배열을 이용한 구현

먼저 N개의 원소들로 구성된 배열 V를 활용한다. 가장 중요한 것은 get 메서드, set 메서드 등 필요하다면 r < 0 또는 r > n – 1 인 경우 예외처리를 해야한다는 것이다.

 

초기화 (initailization)

초기에는 아무 원소도 존재하지 않는 상태이다. O(1) 시간이 소요된다.

초기화 의사코드

초기화 배열의 상태

순회 (Traversal)

Traverse는 array의 모든 원소 V[0], V[1], V[2], …, V[n – 1]을 방문한다. (추가로 출력해도 좋다) 

존재하는 모든 원소를 방문하므로 O(n) 시간이 소요된다.

순회 의사코드

배열을 순회하는 모습

삽입 (Insertion)

작업 add(rank, element)에서는, rank 순위로 새 원소 element가 들어갈 빈 자리를 만들기 위해 V[n – 1], … , V[r]까지의 n – r개의 원소들  순방향으로 이동(shift forward)한다. 이 경우 rank 가 0이면, n개의 원소가 한 칸씩 옮겨야 하므로 O(n) 시간이 소요된다. 구현하면서 예외에 주의하자!

삽입의 의사코드

rank에 element를 삽입하는 모습

삭제 (Deletion)

삽입과 반대로 작업 remove(rank)에서는, 삭제된 원소에 의해 생긴 빈 자리를 채우기 위해 V[r + 1], … , V[n – 1]까지의 n – r – 1개의 원 소들을 역방향으로 이동(shift backward)한다. 이 경우 rank 가 0이면, n개의 원소가 한 칸씩 옮겨야 하므로 O(n) 시간이 소요된다. 구현하면서 예외에 주의하자!

삭제 의사코드

rank에 해당하는 element를 삭제하는 모습

 

성능 (Performance)

* 배열을 이용하여 리스트 ADT를 구현할 경우

데이터구조에 의한 기억장소 사용량: O(n)
size, isEmpty, get, set: O(1)
add, remove: O(n)
addFirst, removeFirst: O(n)
addLast, removeLast: O(1)


* 배열을 원형으로 이용하면
addFirst, removeFirst: O(1)

---

이중연결리스트를 이용한 구현

단일연결리스트를 활용하여 구현할 수 있지만, 이번에는 이중연결리스트를 이용해 구현하는 방법을 배워보자.

이중연결리스트(doubly linked list)를 이용하면 리스트 ADT를 자연스럽게 구현할 수 있다. 이중연결리스트의 노드 구성과 특징은 이전 포스팅을 참고하자.

 

https://mainyoung.tistory.com/21

자료구조 및 실습 - [3] 기초 데이터 구조 (배열, 연결리스트) (1)

 

이를 구현하면서 Header 노드와 Trailer 노드를 적극적으로 활용하겠다.

작업 get(r) 또는 set(r, e)는 O(n) 시간에 지정된 순위 r의 원소를 반환 또는 저장하는 것이다. 또한 연결리스트에서 순위는 1에서 출발로 전제한다.

get과 set 메서드의 의사코드

여기서 주의해야 할 점은 구현하면서 예외(Exception)를 주의해야한다는 것이다. 이중연결리스트를 시각화 하면 다음과 같다.

이중연결리스트의 시각화

초기화 (initailization)

초기에는 아무 노드도 없다. 따라서 Header 노드와 Trailer노드만 서로 연결한다. O(1) 시간이 소요된다.

이중연결리스트의 초기화 의사코드

이중연결리스트의 초기화

순회 (Traversal)

연결리스트의 모든 원소들을 방문하며, Print해도 좋다. O(n) 시간이 소요된다.

이중연결리스트의 의사코드

이때 포인터에 Header의 next를 저장해서 사용한다!

 

삽입 (Insertion)

이중연결리스트의 지정된 순위 r에 원소 e를 삽입하는 작업이다. O(n) 시간이 소요된다.

이번에는 작업 add(rank, X)의 시각화fmf 보자 – 여기서 rank = 3으로 설정했다.

이중연결리스트의 삽입

기존에는 rank 3 에 C가 있었지만, 삽입을 위해 B와 C의 이중연결을 끊고 B와 X, X와 C에 이중연결을 구성한다.

이중연결리스트의 삽입 의사코드

 

삭제 (Deletion)

이중연결리스트의 지정된 순위 r의 노드를 삭제하고 원소를 반환한다. O(n) 시간이 소요된다.

이중연결리스트의 삭제 의사코드

rank 3과 연결된 B와 Trailer의 이중연결을 끊고 B와 Trailer를 이중연결한다. 이후 C를 삭제한다.

 

성능 (Performance)

이중연결리스트를 이용한 리스트 ADT를 구현할 경우 성능은 다음과 같다.

연결리스트의 각 원소에 사용되는 기억장소: O(1)
N개의 원소로 구성된 연결리스트에 의해 사용되는 기억장소: O(n)
size, isEmpty: O(1)
get, set, add, remove: O(n)
addFirst, addLast, removeFirst, removeLast: O(1)

 

배열과 연결리스트의 성능을 요약하자면 다음과 같다.

작업	배열	연결리스트
size, isEmpty	1	1
get, set	1	n
add, remove	n	n
addFirst, removeFirst	n	1
addLast, removeLast	1	1