[Java] List 인터페이스 구현체 - ArrayList와 LinkedList

ArrayList

• List Interface의 구현체이기에 저장 순서가 유지되고 중복을 허용한다.
• 연속적인 데이터의 리스트 (데이터는 연속적으로 리스트에 들어있어야 하며 중간에 빈공간이 있으면 안된다)
• 데이터의 저장 공간으로 배열 사용(배열 기반) - Object[] 배열을 이용하여 요소를 저장: 객체 배열, 다형성(모든 종류의 객체 저장 가능) 
• 기존의 Vector를 개선한 것으로 구현원리와 기능은 동일
• Vector와 달리 ArrayList는 동기화처리X
• 배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근
• 데이터를 리스트 중간에 삽입/삭제 할 경우, 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 자동으로 이동시키기 때문에 삽입/삭제 동작은 느리다.
• 성능을 높이기 위해 미리 용량을 정해서 크게 잡아두면 데이터의 추가 시 도움됨 그러나 비효율적인 메모리 사용하게된다.

ArrayList vs Arrays

배열은 크기를 변경할 수 없는 정적 할당(static allocation) 방식으로 메모리를 관리합니다. 데이터의 크기가 미리 정해져 있는 경우, 배열은 메모리 관리가 용이합니다. 메모리 상에 연속적으로 데이터가 나열되므로, 인덱스를 통한 접근 속도가 빠릅니다. 하지만 인덱스 위치에 있는 데이터를 삭제하더라도 해당 자리는 빈 공간으로 남아있습니다. 배열의 크기가 고정되어 있어 처음 설정한 크기가 너무 크다면 메모리를 낭비할 수 있고, 너무 작게 설정하면 공간이 부족해질 수 있습니다.

반면, ArrayList는 길이가 가변적인 동적 할당(dynamic allocation) 방식입니다. 이는 배열과 달리 메모리 상에 연속적으로 저장되지 않고, 주소를 통해 요소들이 연결된 구조입니다. 때문에 인덱스를 통한 접근 속도는 배열보다 느릴 수 있습니다. ArrayList는 중간에 빈 공간을 허용하지 않아 데이터가 추가되거나 삭제될 때 자동으로 공간을 조정합니다. 하지만 데이터를 객체로 다루기 때문에 적은 양의 데이터를 처리할 때는 배열에 비해 메모리 사용량이 더 많아질 수 있습니다.

---

ArrayList 객체 생성

메서드	설 명
ArrayList()	크기가 10인 ArrayList를 생성
ArrayList(Collection c)	주어진 컬렉션이 저장된 ArrayList를 생성
ArrayList(int initialCapacity)	지정된 초기용량을 갖는 ArrayList를 생성

 

ArrayList 요소 추가

메서드	설 명
boolean add(Object obj)	ArrayList의 마지막에 객체를 추가한다. 추가에 성공하면 true를 반환
void addAll(Collection c)	주어진 컬렉션의 모든 객체를 저장한다.(마지막 index의 뒤로 붙임)

 

ArrayList 요소 삽입

메서드	설 명
void add(int index, Object element)	지정된 위치(index)에 객체를 저장한다. 자리에 있던 기존의 데이터는 뒤로 밀려나기만 할 뿐 삭제되지 않는다.
void addAll(int index, Collection c)	지정한 위치부터 주어진 컬렉션의 데이터를 저장한다. 자리에 있던 기존의 데이터는 뒤로 밀려나기만 할 뿐 삭제되지 않는다.

이때, 데이터 삽입을 하게되면 데이터를 한칸씩 뒤로 밀어야 하기때문에 시간복잡도는 O(n)이다.

ArrayList에서 특정 위치에 요소를 삽입할 때는, 해당 위치가 리스트의 크기(capacity)를 초과하지 않도록 주의해야 한다.
만약 리스트의 크기를 넘어선 위치에 요소를 삽입하려고 하면 IndexOutOfBoundsException 예외가 발생한다.
예를 들어, 리스트에 100번째 인덱스 위치에 요소를 추가하려고 하면 오류가 발생.

리스트의 물리적인 크기(capacity)는 충분할 수 있지만, 논리적인 크기(size)는 실제로 저장된 요소의 개수를 나타내는데 ArrayList는 요소들이 연속적으로 저장되는 자료구조이기 때문에, 논리적인 크기를 넘어서는 위치에 요소를 추가하려고 하면 문제가 발생한다.
예를 들어, 리스트의 논리적 크기가 5일 때, 7번째 위치에 요소를 삽입하려고 하면 논리적인 크기를 초과하게 되어 IndexOutOfBoundsException이 발생하게 되는 것이다.

 

ArrayList 요소 제거

메서드	설 명
Object remove(int index)	지정된 위치(index)에 있는 객체를 제거한다.
boolean remove(Object obj)	지정된 객체를 제거한다.(성공하면 true)
boolean removeAll(Collection c)	지정한 컬렉션에 저장된 것과 동일한 객체들을 ArrayList에서 제거한다.
void clear()	ArrayList를 완전히 비운다.
boolean retainAll(Collection c)	ArrayList에 저장된 객체 중에서 주어진 컬렉션과 공통된 것들만 남기고 제거한다. (removeAll 반대 버전)

ArrayList에서 요소 제거 과정은 삭제할 데이터아래의 데이터를 한칸씩 위로 복사해서 삭제할 데이터를 덮어쓰고 데이터가 모두 한칸씩 이동하면 마지막 데이터를 null로 변경하게된다. 그리고 마지막에 size값을 감소시킨다. 이때 마지막 데이터를 삭제하게되면 데이터의 복사는 생략된다.

ArrayList 요소 검색

메서드	설 명
boolean isEmpty()	ArrayList가 비어있는지 확인한다.
boolean contains(Object obj)	지정된 객체(obj)가 ArrayList에 포함되어 있는지 확인한다.
boolean removeAll(Collection c)	지정된 객체(obj)가 저장된 위치를 찾아 반환한다.
int indexOf(Object obj)	지정된 객체(obj)가 저장된 위치를 뒤에서 부터 역방향으로 찾아 반환한다.

 

ArrayList 요소 얻기

시간 복잡도는 O(1)이다.

메서드	설 명
Object get(in index)	지정된 위치(index)에 저장된 객체를 반환한다.
List subList(int fromIndex, int toIndex)	fromIndex부터 toIndex사이에 저장된 객체를 반환한다.

 

ArrayList 요소 변경

메서드	설 명
Object set(int index, Object obj)	주어진 객체(obj)를 지정한 위치(index)에 저장한다. 자리에 있던 기존의 데이터는 삭제되고 새로운 데이터가 대체되어 들어간다.

 

 

ArrayList 용량 확장

메서드	설 명
int size()	ArrayList에 저장된 객체의 개수를 반환한다.
void ensureCapacity(int minCapacity)	ArrayList의 용량이 최소한 minCapacity가 되도록 한다.
void trimToSize()	용량의 크기에 맞게 줄인다 (빈 공간을 없앤다.)

 

ArrayList는 생성할때 용량이 정할 수 있지만, 데이터가 추가되면서 자동으로 용량(Capacity)을 늘려준다.
만일 정해진 용량보다 넘게 데이터를 적재할 경우, 자체적으로 내부 배열을 큰 사이즈로 새로 만들고 기존의 배열에서 요소들을 복사함으로써, 간접적으로 리스트의 용량을 확장시키게 된다.

하지만 이러한 가변적인 동작은 리스트를 다루는데에는 편하지만, 배열 복사 동작 자체가 성능이 그리 좋지않아 오버헤드(Overhead)를 발생 시키게 된다.

 

ArrayList 복사

메서드	설 명
boolean isEmpty()	ArrayList가 비어있는지 확인한다.
boolean contains(Object obj)	지정된 객체(obj)가 ArrayList에 포함되어 있는지 확인한다.
boolean removeAll(Collection c)	지정된 객체(obj)가 저장된 위치를 찾아 반환한다.
int indexOf(Object obj)	지정된 객체(obj)가 저장된 위치를 뒤에서 부터 역방향으로 찾아 반환한다.

ArrayList<Integer> number = new ArrayList<>();
number.add(1);
number.add(3);
number.add(5);

// ArrayList는 내부적으로 Object[] 배열로 저장하기 때문에 형변환이 필요함
ArrayList<Integer> cloneNumber = (ArrayList<Integer>) number.clone();

System.out.println("ArrayList: " + number); // [1, 3, 5]
System.out.println("Cloned ArrayList: " + cloneNumber); // [1, 3, 5]

 

ArrayList 배열반환

메서드	설 명
Object[] toArray()	ArrayList에 저장된 모든 객체들을 배열로 반환한다.
Object[] toArray(Obejct[] objArr)	ArrayList에 저장된 모든 객체들을 배열 objArr에 담아 반환한다.

 

 

 

ArrayList 정렬

ArrayList를 정렬할때 주의할점은 sort() 메서드는 정렬된 값을 반환하는 것이 아닌, 원본 리스트 자체를 변경 시킨다.

메서드	설 명
void sort(Comparator c)	지정된 정렬기준(c)으로 ArrayList를 정렬한다.

 

 

ArrayList 이터레이터

메서드	설 명
Iterator iterator()	ArrayList의 Iterator객체를 반환한다.
ListIterator listIterator()	ArrayList의 ListIterator를 반환한다
ListIterator listIterator(int index)	ArrayList의 지정된 위치부터 시작하는 ListIterator를 반환한다.

 

---

LinkedList

• 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징
• ArrayList는 내부적으로 배열을 이용하여 메서드로 이리저리 조작이 가능하게 만든 컬렉션이라면, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조
• ArrayList에 비해 데이터 접근성이 나쁘다. 그것을 개선하는 것이 더블리 링크드 리스트(Doubly Linked List)

Doubly Linked List 이중 연결 리스트로 데이터 접근성을 향상시키기 위해 다음요소 뿐만 아니라 이전 요소에 대한 노드의 주소를 추가로 저장한다.

또 추가로 더 보완한 버전이
Doubly Circular Linked List
맨 마지막 요소에서 맨 앞 요소를 연결하고 맨 앞 요소에서 맨 마지막 요소까지도 연결해서 맨앞에서 이전으로 가면 맨뒤로, 맨뒤에서 앞으로 가면 맨 앞으로 넘어가도록 해서 탐색 시간을 줄일 수 있다.

실제 자바는 이중 연결 리스트(Doubly Linked List)로 구현되어 있다.

 

ArrayList와 LinkedList비교

1. 순차적으로 데이터를 추가/삭제  - ArrayList가 빠름
2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름
3. 접근 시간 - ArrayList가 빠름

관련 메소드들

LinkedList 클래스 역시 List 인터페이스를 구현하므로, ArrayList 클래스와 사용할 수 있는 메소드가 거의 같다.

다만 LinkedList는 List 자료구조 외에도 Stack이나 Queue 자료구조로서도 이용이 가능하기 때문에 이를 위한 메서드들도 구현되어 있어 내부 메서드 갯수가 컬렉션중에 가장 많다고 보면 된다.

 

 

addFirst()와 addLast()는 요소를 첫번째, 마지막에 추가하는 것이기 때문에 O(1) 의 시간이 걸린다.
그러나 중간 삽입일 경우 중간에 삽입할 위치까지의 탐색을 필요하기 때문에 O(N)의 시간이 걸린다.
remove 메서드 역시 add 메서드 처럼 removeFirst() 와 removeLast() 는 O(1), 그외에는 탐색 시간이 필요하기에 O(N)이 걸린다.

 

 

LinkedList는 리스트 용도로서 뿐만 아니라, 구조 특성상 Stack이나 Queue 로서도 이용이 가능하다. 그래서 아래와 같이 스택과 큐에 관한 전용 메서드를 별도로 제공한다.

메서드	설명
Object element()	LinkedList에 첫 번째 노드를 반환
boolean offer(Obejct obj)	지정된 객체(obj)를 LinkedList의 끝에 추가. 성공하면 true 실패하면 false
Object peek()	LinkedList의 첫 번째 요소를 반환
Object poll()	LinkedList의 첫 번째 요소를 반환 LInkedList의 요소에서는 제거된다.
void push(Object obj)	맨 앞에 객체(obj)를 추가 (addFirst와 동일)
Iterator descendingItorator()	역순으로 조회하기 위한 DescendingItorator를 반환
Object getFrist()	LinkedList의 첫번째 노드를 반환
Object getLast()	LinkedList의 마지막 노드를 반환
boolean offerFirst(Object obj)	지정된 객체(obj)를 LinkedList의 맨 앞에 추가, 성공하면 ture
boolean offerLast(Object obj)	지정된 객체(obj)를 LinkedList의 맨 뒤에 추가, 성공하면 ture
Object peakFirst()	첫번째 노드를 반환
Object peakLast()	마지막 노드를 반환
Object pollFirst()	첫번째 노드를 반환하면서 제거
Object pollLast()	마지막 노드를 반환하면서 제거
Object pop()	첫번째 노드를 제거 (removeFirst와 동일)
boolean removeFirstOccurrence( Obejct obj)	첫번째로 일치하는 객체를 제거
boolean removeLastOccurrence( Obejct obj)	마지막으로 일치하는 객체를 제거

 

 

https://inpa.tistory.com/entry/JAVA-%E2%98%95-LinkedList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%99%84%EB%B2%BD-%EC%A0%95%EB%B3%B5%ED%95%98%EA%B8%B0

관련 메소드들은 해당 게시글을 참고하자