컴언

'컴퓨터과학'에 해당되는 글 1건

  1. 리스트 (List) - 1. ArrayList 구현 (1)

리스트 (List) - 1. ArrayList 구현

자료구조

10일간의 추석 연휴 오예 신난다 동안 뭐를 할지 고민하다가 평소에 하겠다고 다짐만 하고 막상 하지는 못 했던 자료 구조 정리를 해보려고 합니다. 특히 제가 내년 초에 있을 기술 면접 대비도 해야 하기 때문에 기술 면접에서는 어떻게 등장할 수 있을지도 초점을 맞춰서 써보도록 하려고요. 제가 많이 부족하지만 벼락치기 대비에 유용한 가이드가 되었으면 좋겠습니다.


리스트

[정의] 순서가 있는 원소들의 집합 (An ordered collection of elements)

맨 처음으로 다룰 자료 구조는 리스트 추상 자료형(Abstract Data Type, ADT) 입니다.

여담: 순서가 없는 원소들의 집합은 Set! ㅎㅎ


대표적인 연산 종류

1. list()

생성자 constructor 입니다. 빈 리스트를 생성합니다.

필드에는 

(1) Object[] items (리스트 원소들의 array)

(2) int numItems (원소의 개수)

가 있습니다.

2. void add(Object ob)

리스트의 끝에 ob 라는 Object 를 추가합니다.

3. void add(int pos, Object ob)

리스트의 pos 위치에 ob 라는 Object 를 추가합니다. 

*** 이 과정에서 원래 pos 위치에 있던 원소부터 size() 위치(맨 끝)에 있던 원소들은 ob 를 위한 공간을 만들어주기 위해 한 칸씩 오른쪽으로 이동하겠죠?

(단, pos0보다 작거나 size() 보다 크면 에러)

4. boolean contains(Object ob)

ob 라는 Object 가 리스트에 있다면 true 를 반환합니다.  

5. int size()

리스트에 있는 원소의 개를 반환합니다.

6. boolean isEmpty()

리스트가 비어있으true 를 반환합니다.

7. Object get(int pos)

pos 위치에 있는 원소를 반환합니다. 

(단, pos  0보다 작거나 pos  size()면 에러, 0-indexing 이기 때문에 pos 는 size()보다 작아야겠죠.)

8. Object remove(int pos)

pos 위치에 있는 원소를 제거한 뒤 제거된 원소를 반환합니다. 

***  과정에서 pos+1 에 위치한 원소부터 size() 에 있는 원소들은 없어진 원소 공간을 채우기 위해 한 칸씩 오른쪽으로 이동합니다. 

(단, pos 가 0보다 작거나 pos  size()면  에러, 0-indexing 이기 때문에 pos 는 size()보다 작아야겠죠.)


리스트의 구현 방법

구현 1 - ArrayList
ArrayList 는 array 를 이용한 List 구현 방법입니다. 

1. 생성자
생성자는 필드들을 initialize 해서 빈 리스트를 생성해야합니다. 원소의 개수 필드인 numItems 는 0 로 설정되야하겠고요. 원소들을 담을 array인 items 에 조금 문제가 있습니다. items 를 null 로 initialize 하자니... 나중에 메소드 쓸 때 items 가 null 인 경우를 고려해야하니 문제가 될 것 같습니다. 해답은 바로 임의의 초기 크기를 가진 array 를 만드는 겁니다. 초기 크기 INITIAL_SIZE 는 static final 필드로 정하겠습니다.

우선 10을 INITIAL_SIZE 로 정하도록 합시다. 실제 사용 시에는 어떤 상황에서 리스트가 쓰이냐에 따라 적절한 초기 크기를 정해줘야 합니다.  바로 다음에 add 메소드를 구현하면서 느끼시겠지만, 초기 크기가 크면 공간이 부족해지는 상황 전에 add 를 많이 쓸 수 있다는 장점이 있습니다. 하지만 초기 크기를 너무 크게 잡아줘서 공간을 다 쓰지도 못하고 끝나는 메모리 낭비가 될 수도 있습니다. 결국 상황에 따라 적절한 INITIAL_SIZE 를 설정하는 게 중요하겠죠.

1-a. ArrayList 생성자

2. add 메소드
우선 파라미터가 하나인 add를 구현해보도록 합니다. 간단하게 Object 를 리스트의 끝에 추가시키면 되는 메소드입니다. 그런데 여기서 중요한 문제가 하나 있어요.

"array 에 더이상 공간이 없는 경우는?"

기존 array에 더이상 새 Object 가 들어갈 공간이 없다면 어떻게 할까요? 

(1) 더 큰 array 를 만들고, 
(2) 새 array 에 원래 있던 원소들을 복사를 하고 나서야

새로운 Object 를 추가시킬 수 있을겁니다. 게다가 이 문제는 파라미터가 하나인 add(Object ob)뿐만 아니라 파라미터가 두개인 add(int pos, Object ob)에도 해당되는 문제입니다. 그렇다면 (1) - (2) 과정을 하나의 메소드로 만들어버리면 두 add에서 재활용할 수 있겠죠. 그 새로운 메소드(array 크기 확장)를 expandArray 라고 이름 짓겠습니다. 그리고 이 expandArray는 유저가 알 필요 없는, 구현을 위해서만 사용되는 메소드이기 때문에 private 메소드로 만듭니다.

2-a. add(Object ob) 와 expandArray()


*** 맨 뒤에 항목을 추가하는 add의 시간 복잡도는 O(1) 혹은 O(n) 입니다. 이게 일반적인 표기인지는 잘 모르겠습니다만... (Oracle 에서는 Amortized O(1) 이라는 표현을 쓰긴 합니다만... 일반적인 Worst Case 시간복잡도하고는 다른 개념입니다) 뒤에 항목을 추가하는 연산 자체는 O(1) 이 맞습니다. 하지만 우리가 크기를 지정해줘야하는 array를 쓰고 있어서 가끔 공간이 부족해 expandArray() 를 해줘야하는 상황이 있잖아요. 이 공간 확장의 경우 때문에 O(n) 의 상황도 생기는 것입니다.

이제 파라미터가 두 개인 add(int pos, Object ob) 의 경우를 살펴볼게요. 방금 구현한 파라미터 한 개인 add에 비해 파라미터가 하나 더 늘었다는 차이밖에 없는데요, 중요하게 점검할 부분이 있습니다.

"pos 에 올바르지 않은 값이 입력되는 경우"

pos 의 값이 올바르지 않은 경우(예를 들어 음수나 array size 보다 큰 수)에 예외처리를 해줘야합니다. 따라서 
(1) pos 가 올바른 범위에 있는지 확인합니다. 올바른 범위가 아니면 IndexOutOfBoundsException 을 throw 합니다. 
(2 pos 가 올바른 값이었다면, array 에 공간이 있는지 확인해야합니다. 공간이 없다면 expandArray() 를 호출해 array크기를 확장합니다.
(3) 그 다음, pos ~ numItems-1 까지 위치의 모든 item 들을 오른쪽으로 한 칸씩 이동시켜서 새 Object 가 들어갈 공간을 만들어줍니다. 
(4) 이 모든 과정을 한 뒤에야 새 Object 를 pos 위치에 삽입하고, numItems에 1을 더합니다.

2-b. add(int pos, Object ob)

*** 특정 위치에 항목을 추가하는 add의 시간 복잡도는 O(n) 입니다. 맨 뒤에 추가하는 add 와는 다르게, array 를 traverse 해야하기 때문이죠.



3. remove 메소드
remove 메소드 에는 지울 원소의 위치가 파라미터로 주어집니다. 그래서 
(1) 먼저 pos 가 올바른 범위에 있는지 확인을 해야합니다.
(2) void 가 아니고 지운 Object 를 반환해줘야 하기 때문에 지우기 전 지울 Object 를 임시로 저장해줘야합니다. 
(3) 그 다음 pos+1 ~ numItems-1 까지 위치의 원소들을 왼쪽으로 한 칸씩 이동해줍니다. 이 과정에서 우리가 지워야 하는 items[pos] 는 덮여쓰여지기 때문에 사실상 지워진 것이 됩니다. 
(4) 그리고 깜박할 수 있는 것 하나! 마지막 원소가 있던 원래의 자리에는 그대로 그 항목이 있습니다.

예를 들어

 pos

item 0

item 1 

item 2 

item 3

item 4 

item 5 

 value

d

e

f


와 같은 array 있을 때 item 3 을 지웠다고 합시다. 그러면 아래와 같이 한 칸씩 왼쪽으로 이동시킵니다.

 pos

item 0

item 1 

item 2 

item 3

item 4 

item 5

value

e

f

f



그런데!! 5 위치에 이동시킨 원래 항목이 그대로 남아있습니다!! 따라서 이 마지막 항목이 원래 있던 위치의 항목(이 경우 item 5)도 삭제해줘야 합니다.

(5) 그리고 나서 numItems 에서 1을 빼고, 지운 Object 를 반환해주면 되는거죠.

3-a. remove(int pos)

*** remove의 시간 복잡도는 O(n) 입니다. ob 를 위한 공간을 만들 때의 for loop 때문이죠. 

4. get 메소드

주어진 위치에 있는 항목을 반환해주면 되는데요 ㅎㅎ 쉽습니다. 
(1) pos 가 파라미터로 들어오니깐 범위 체크 해주고요, 
(2) 그 다음 items[pos] 반환해주면 끝! 

4-a. get(int pos)

get의 시간 복잡도는 O(1) 인데, 그 이유는 array 를 사용하는 것에서 찾을 수 있습니다. array access 는 메모리 시작 주소에 pos 위치를 더하기만 함으로써 access 하는 것이거든요. 결국 access = 사칙 연산이라고 볼 수 있기 때문에 O(1) 이라고 이해하는 것은 어떨까요?


5. iterator 메소드
어떤 자료 구조를 쓸 때 그 자료 구조를 iterate(순회) 할 일이 많습니다. 방금 구현한 get 메소드를 이용해서 우리의 ArrayList 를 순회하는 iterator 라는 것을 만들 수 있는데요, 중요한 포인트가 많으니 유심히 보도록 합시다. 되게 쉬운 개념인데 저는 자료 구조 수업 들을 때 신경 별로 안쓰다가 간단한 Iterator 문제에서 많이 틀렸었습니다 ㅠㅠ

자바에서 iteratorCollectionimplements 하는 모든 자료 구조에서 필요한 메소드입니다. Iterator 인터페이스는 java.util 에 정의되어 있고요, iterator 메소드는 이 Iterator 을 반환해줘야 합니다.

Iterator 은 리스트의 항목을 가리키고 있는 손가락 혹은 포인터처럼 생각하시면 쉽습니다. 

(1) 처음 Iterator 가 생성되면, 그 Iterator가장 첫번째 항목을 가리니다. 
(2) Iterator 에는 next 라는 메소드가 있는데, 이 next 라는 단어가 여러분을 혼란스럽게 할 수 있으니 조심하세요. 
(3) next 메소드는 현재 Iterator가리키고 있는 항목을 반환함과 동시에 포인터(손가락)가 다음(next) 항목을 가리키게 합니다. 절대로 다음 항목을 반환하는 게 아닌거죠... 현재 가리키고 있는 항목을 반환하는 겁니다!! next 라고 이름 붙여진 것은 호출되면 다음 항목을 가리키기 때문에 입니다.


Iterator 가 어떻게 작동하는지 예제와 함께 알아봅시다. 아래와 같은 Fruits 리스트가 있습니다.

사과 

배 

바나나 

딸기 

 


1. 이 리스트에 대한 Iterator 을 생성하면, Iterator 은 아래처럼 맨 처음 항목인 사과를 가리키게 됩니다.

사과 

배 

바나나 

딸기 

 

 


 


 

2. 이제 next 를 호출하면 현재 가리키고 있는 사과를 반환하고, 리스트의 Iterator 은 아래처럼 다음 항목인 배를 가리키게 됩니다.

사과 

배 

바나나 

딸기 

 

 

 

 


 

3. next 를 호출 -> 배를 반환.  포인터는 바나나를 가리킴.

사과 

배 

바나나 

딸기 

 

 

 

 


 

4. next 를 호출 -> 바나나를 반환.  포인터는 딸기를 가리킴.

사과 

배 

바나나 

딸기 

 

 

 

 

 
5. (주의) 위와 같은 상황의 Iterator 의 hasNext 메소드는 true 를 반환합니다! 왜? 아직 access 하지 못한 항목이 하나 남았잖아요. 다시 한번 next 를 호출하면 딸기를 반환할 것이고 그제야 아래와 같은 그림이 됩니다.

사과 

배 

바나나 

딸기 

 

 

 

 


 

6. 이제 iterator 가 리스트의 바깥으로 나가버렸습니다. 이제 hasNext 메서드는 false 를 반환하고요, 이 상황에서 next 를 호출하면 NoSuchElementException 응~그런거없어 에러를 뿜는 걸 볼 수 있을겁니다.



아래는 우리 List 클래스를 위한 Iterator 을 구현에 대한 설명입니다.


우선 ListIterator 라는 새로운 클래스를 만들건데요, 두 가지 필드가 있습니다. 

(1) iterate(순회) 될 List

(2) 포인터(손가락) -- 인덱스라고 합시다 ㅎㅎ


그리고 우리의 ArrayList 클래스에서는 아래처럼 iterator 라는 메소드를 만들어줘야 합니다. 이 메소드는 ListIterator 의 생성자를 호출해 자기 자신을 List 에 반환합니다.


아까 Iterator 라는 인터페이스가 있다고 말씀드린 거 기억 나세요? ListIterator 은 이 인터페이스를 implements 하기 때문에 세 가지 메소드를 구현해야합니다. 아까 봤던 hasNext 와 next, 그리고 선택적으로 remove 라는 메소드를 구현해야 합니다. 아래에 간단히 구현한 ListIterator 클래스를 참고해주세요.


6. contains 메소드
contains 는 파라미터로 들어온 Object 가 List 가 존재하면 true 를 반환합니다. items 를 순회하며 원하는 Object 가 있는지 비교해가며 체크하면 됩니다. 아래 구현을 보시죠.

7. isEmpty 메소드
ㅎㅎ 이제 막판이네요. isEmpty 는 List 가 비어있는지 여부를 반환합니다. 즉 List 원소 개수가 0이면 true 를 반환합니다.

8. size 메소드
size 는 List 원소 개수를 반환합니다. 지금까지 많이 호출했던 메소드인데 ㅋㅋ 이제야 구현하는군요.


구현 2 - LinkedList


이번 글에서는 array 를 이용한 List 구현인 ArrayList 를 알아봤는데요, LinkedList 라는 구현 방법도 있습니다. 다음 편에서 알아보도록 하겠습니다.