[Java]컬렉션 프레임웍 (2) - ArrayList, LinkedList

ArrayList

ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일하다.

ArrayList와 달리 Vector는 자체적으로 동기화 처리가 되어 있다.

List인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.

데이터의 저장공간으로 배열을 사용한다. (배열 기반)

Vector클래스의 소스 코드

Vector클래스의 소스 코드를 보면 객체를 담기 위한 배열 타입으로 Object[]를 사용한다.

즉, 최고 조상인 Object클래스를 사용해 모든 종류의 객체를 저장 할 수 있다. (다형성)

---

ArrayList의 메서드

생성자	ArrayList()	기본 생성자
	ArrayList(Collection c)	매개변수로 Collection을 주면 해당 Collection을 저장하는 ArrayList를 생성한다.
	ArrayList(int initialCapacity)	배열의 길이를 지정한다.
추가	boolean add(Object o)	객체를 추가한다. (성공하면 true, 실패하면 false)
	void add(int index, Object element)	객체를 저장할 위치를 지정하고 추가한다.
	boolean addAll(Collection c)	컬렉션이 가지고 있는 요소를 추가한다.
	boolean addAll(int index, Collection c)	컬렉션을 저장할 위치를 지정하고 추가한다.
삭제	boolean remove(Object o)	저장한것을 삭제한다.
	Object remove(int index)	특정 위치에 있는 객체를 삭제한다.
	boolean removeAll(Collection c)	특정 컬렉션에 있는 객체를 삭제한다.
	void clear()	모든 객체를 삭제한다.
검색	int indexOf(Object o)	몇번째에 객체(o)가 저장되었는지 찾는다. (못찾으면 -1 반환) 오른쪽에서 왼쪽으로 찾는다.
	int lastIndexOf(Object o)	몇번째에 객체(o)가 저장되었는지 찾는다. (못찾으면 -1 반환) 왼쪽에서 오른쪽으로 찾는다.
	boolean contains(Object o)	지정된 객체가 존재하는지 확인한다.
	Object get(int index)	특정 위치에 있는 객체를 읽는다.
	Object set(int index, Object element)	특정 위치에 있는 객체를 변경한다.
기타	List subList(int fromIndex, int toIndex)	from~to까지의 객체를 뽑아서 새로운 List를 만든다.
	Object[] toArray()	ArrayList의 객체배열을 반환한다.
	Object[] toArray(Object[] a)
	boolean isEmpty()	ArrayList가 비어있는지 확인한다.
	void trimToSize()	ArrayList의 빈공간을 제거한다.
	int size()	ArrayList에 저장된 객체의 갯수를 반환한다.

---

ArrayList에 저장된 객체의 삭제과정

ArrayList에 저장된 세 번째 데이터(data [2])를 삭제하는 과정은 다음과 같다.

① list.remove(2);를 호출 ( index가 2인 객체 삭제 )

② 삭제할 데이터 아래의 데이터를 한 칸씩 위로 복사해서 삭제할 데이터를 덮어쓴다.

③ 데이터가 모두 한 칸씩 이동했으므로 마지막 데이터는 null로 변경한다.

④ 데이터가 삭제되어 데이터의 개수가 줄었으므로 size의 값을 감소시킨다.

 

만약 data [4] 번 인덱스의 4를 제거한다면 ②번 과정이 생략되고 ③, ④번 과정만 진행할 것이다.

그렇다면 과정 하나가 생략됨으로 빠르고 효율이 좋아진다.

그렇기에 가능한 ②번 과정을 생략하고 진행하는 방향으로 설계하는 것이 좋다.

 

반복문 for문을 통해 ArrayList의 객체를 모두 삭제한다면 int i = list.size()로 해야 한다.

ArrayList에 저장된 첫 번째 객체부터 삭제하는 경우 (배열 복사 발생)

이렇게 i가 0부터 올라가는 for문은 인덱스가 삭제되면 계속 뒤에 인덱스 값들이 덮어쓰기 때문에 1 하고 3이 남게 된다.

ArrayList에 저장된 마지막 객체부터 삭제하는 경우 (배열 복사 발생안함)

위 코드와 같이 int i = list.size()로 해서 마지막 객체부터 삭제를 하면 덮어쓰는 과정이 없기 때문에

모든 객체가 삭제되는 것을 확인할 수 있다.

---

LinkedList

배열의 장단점

▶ 장점 : 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.

▶ 단점 1 : 크기를 변경할 수 없다.
   - 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 한다.
   - 크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비된다.

▶ 단점 2 : 비순차적(중간에)인 데이터의 추가, 삭제에 시간이 많이 걸린다.
   - 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 한다.
   - 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

배열의 단점으로는 크기 변경이 불가능하다는 것과, 추가와 삭제에 시간이 많이 걸린다는 것이다.

그러한 배열의 단점을 보완한 것이 LinkedList이다.

배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)한다.

배열은 각 요소가 연속적이기 때문에 배열의 값들 붙어있어 배열의 다음 값의 주소를 알 수 있다.

하지만 링크드 리스트는 값들이 붙어있지 않다. 가까이 있을 수도 있고 멀리 떨어져 있을수도 있다.

이렇게 링크드 리스트는 하나하나마다 불연속적이다. 그런 하나하나를 노드(Node)라고 부른다.

이렇게 각 노드들은 다음 노드의 참조 변수(next)와 값(obj)을 가지고 있다.

즉, 주소가 불연속적이라도 노드가 서로서로 링크되어 연결되어있는 것이다.

그렇기에 데이터를 삭제할 때도 단 한 번의 참조 변경만으로도 가능하다.

예를 들어 1번 → 2번 → 3번 이렇게 가리키고 있을 때

2번을 빼고 싶다면 1번이 가리키는 노드가 2번이 아니라 3번으로 바꾸기만 하면 된다.

데이터를 추가하는 것도 한 번의 Node객체 생성과 두 번의 참조 변경만으로 가능하다.

이렇게 0x350의 객체를 생성하고 0x500의 객체가 자신을 가리키게 하고

생성된 0x350은 다음 노드를 가리키기만 하면 된다.

---

이중 연결 리스트

하지만, 배열의 단점을 보완한 이러한 링크드 리스트에도 단점이 있다.

배열은 연속적이기 때문에 데이터에 접근하기가 쉽다. 서로서로 연속되어 있으니 찾는 값이 어디 있어도 쉽게 찾을 수 있다.

반면에 링크드 리스트는 1번이 2번에 연결되고 2번이 3번에 연결되어 있으니 하나하나 찾아서 가야 한다.

즉, 첫 번째 요소는 두 번째 요소의 위치만 알지 세 번째 요소의 위치는 모르기 때문이다.

링크드 리스트(linked list) - 연결리스트. 접근성이 나쁨

그렇기에 이러한 단점을 보완한 것이 더블리 링크드 리스트(dobly linked lsit)이다.

더블리 링크드 리스트(doubly linked list) - 이중 연결리스트, 접근성 향상

더블리 링크드 리스트는 앞의 노드와 뒤의 노드 모두 연결이 되어있어서 연결 리스트에 비해 접근성이 향상되었다.

그렇지만 여전히 한 번에 이동할 수는 없다. 앞의 노드와 뒤의 노드만 연결되어 있기 때문이다.

그렇게 더블리 링크드 리스트에서 조금 더 보완한 것이 더블리 써큘러 링크드 리스트(doubly circular linked list)이다.

더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스트

더블리 써큘러 링크드 리스트는 제일 끝 노드와 제일 첫 노드가 서로서로 연결이 되어있기 때문에 더 효율이 좋다.

위 이미지에서 3번 노드를 찾는다고 가정하면 제일 끝으로 이동해 한번만 이동하면 되기에 훨씬 수월해졌다.

---

ArrayList와 LinkedList의 성능 비교

비교 결과 (단위 = ms)

① 순차적으로 데이터를 추가/삭제 - ArrayList

② 비순차적으로 데이터를 추가/삭제 - LinkedList

③ 접근시간(access time) - ArrayList

배열은 인덱스가 n인 데이터의 주소를 구할 때 배열의 주소 + n * 데이터 타입의 크기만 구하면 바로 알 수 있다.

반면에 링크드 리스트는 노드를 하나하나 이어서 가야 하기에 오래 걸린다.