ArrayList, LinkedList

김운채·2023년 5월 16일

ArrayList Collection Java List linkedlist

TIL

목록 보기

11/22

List

저번에 배열에 관련한 글을 올렸었다.

배열은 크기가 고정되어있기 때문에 한계가 있는 자료형이다. 근데 난 천재가 아니라서 프로그래밍 중에 배열의 크기를 예측해서 생성할 수 없다.🤷‍♀️

이 문제를 타파하기 위해 List가 만들어졌다. List 는 메모리가 허용하는 한 계속 해서 데이터를 추가 할 수 있도록 만든 자료형 클래스이다.

List 인터페이스는 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용된다.

java.util.List 는 인터페이스 클래스이며, java.util.Collection 인터페이스를 구현한 것이다. 아래에서 골라쓰면 된다.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

List<String> listA = new ArrayList<String>();
List<String> listB = new LinkedList<String>();
List<String> listC = new Vector<String>();
List<String> listD = new Stack<String>();

리스트의 특징

1) 리스트(List)는 크기 조절이 가능하다.
2) 리스트(List)는 초기 크기를 지정하지 않아도 된다.
3) 빈틈없는 데이터의 적재라는 장점을 가진다. 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다.
=> 원소를 삭제했을 때 삭제된 데이터 뒤 원소로 빈틈없이 연속적으로 위치시킨다.
4) 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자)
5) 불연속적으로 메모리 공간을 차지한다.
=> 연속적인 메모리 공간에 데이터들이 연관되며 포인터를 통해 각 데이터들이 연결

ArrayList

ArrayList는 List 인터페이스를 구현하기 때문에, 데이터의 저장순서가 유지되고 중복을 허용한다.
ArrayList는 기존의 Vector를 개선한 것으로 Vector와 구현원리와 기능적인 측면에서 동일하다고 할 수 있다.

자바에서는 배열의 크기가 고정되어있다. Java의 Collection 중 ArrayList 클래스는 이러한 문제점을 해결해준다. 바로 가변적인 크기의 배열 기능을 제공하는 것이다.

어떻게 배열크기를 늘리는 지는 밑에서 자세하게 다루겠지만, 대충 과정은 이렇다.👇

ArrayList는 Object배열을 이용해서 데이터를 순차적으로 저장한다.
예를 들어 첫번째로 들어온 객체는 Object 배열의 0번째 위치에 저장되고, 그 다음에 저장하는 객체는 1번째 위치에 저장된다.
이런식으로 쭉 저장되다가 더이상 공간이 없으면 보다 큰 새로운 배열을 만들어서 기존 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다.

public class ArrayList extends AbstractList
	implements List, RandomAccess, Cloneable, java.io.Serializiable{
		...
        transient Object[] elementData; //Object배열
        ...
}

ArrayList 는 elementData라는 이름의 Object배열을 멤버변수로 선언하고 있다는 것을 알 수 있다. 선언된 배열의 타입이 모든 객체의 최고조상인 Object 이기 때문에 모든 종류의 객체를 담을 수 있다.

ArrayList 선언

ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<String> list2 = new ArrayList<>(); // 타입 생략 가능
ArrayList<Product> pList = new ArrayList<>(); // 타입으로 클래스도 가능

선언 시 자료의 안정성을 위해 제네릭(Generic) 방식으로 타입을 미리 지정해주어 같은 타입의 객체들만 리스트에 추가가 가능하다.
생성자 타입 파라미터는 생략이 가능하며 클래스를 타입 파라미터로 지정이 가능해 더욱 다양한 방식의 사용이 가능하다.

ArrayList 추가

ArrayList를 생성한 후 add() 메소드로 값을 추가할 수 있다.

add(Object) : ArrayList의 마지막에 데이터를 추가
add(int index, Object) : ArrayList의 index에 데이터를 추가

public class ArrayListDemo {
	public static void main(String[] args)  {
		ArrayList<String> al = new ArrayList<>();
		
		al.add("Hello");
		al.add("Hello");
		al.add(1, "World");
		
		System.out.print(al);
	}
}

[Hello, World, Hello]

❗ 여기서 add() 를 졸라 많이 하면 배열의 공간이 부족해질 것이다. ArrayList가 자동으로 크기를 늘려준다고 했으니, 여기서 add 메서드를 살펴 보면서 과정을 확인해보자.

ArrayList 의 크기 증가 과정

add()메서드를 살펴보면 add(e, elementData, size) 라는 메서드를 호출하고 있다.

elementData : elementData는 ArrayList 내부에 저장하고 있는 배열이다. 여기에 우리가 다루는 객체들이 담겨있다. ArrayList도 객체들을 배열로 저장하고 있는 것을 확인할 수 있다.
size : size는 ArrayList 내부의 private 필드이다. 리스트에 몇 개의 데이터를 저장하고 있는지에 대한 정보이다.

🤔 그럼 이 add메서드를 또 까보자.

s == elementData.length 라면, grow() 메서드를 호출하도록 되어있다.
이 부분이 바로 배열의 크기가 부족할 때 배열을 확장시켜주는 부분이다.

🤔 그럼 이 grow()메서드도 까보자고

grow() 메서드 return 값을 보면 grow(size + 1)이라는 메서드를 리턴하고 있다. 여기서 size는 ArrayList에 들어있는 객체의 개수다. 🤔 이놈가지고 뭘 하는지 또 까보자.

return 값을 보면 Arrays.copyOf 메서드를 사용하는 것을 볼 수 있고 두 번째 인자에 newCapacity(minCapacity)를 넣어준 것을 볼 수 있다.
copyOf 함수는 두 번째 인자 크기만큼 배열을 만든 후 첫 번째 인자에서 받은 배열을 복사해서 넘겨주는거다.

이런식으로 공간이 찼을때 자동으로 늘려주는 것이었다.

💁‍♀️ 그럼 얼마나 늘려주는지도 함 봐보자.

newCapacity를 초기화하는 과정을 보면 (이전 배열 크기) + (이전 배열 크기 / 2)인 것을 볼 수 있다. 1.5배 정도로 배열의 크기를 확장하는 것이다.

그럼 ArrayList는 꽉찼을때 1.5배로 크기를 늘려준다는 것을 알 수 있다.

ArrayList 값 변경

ArrayList 값 변경은 set() 메서드를 사용한다.

set(int index, Object)

set()을 사용하기 위해서는 바꾸려면 데이터의 위치Index를 알아야 변경이 가능하다.

ArrayList 값 삭제

ArrayList 값을 삭제하는 방법에는 remove()와 clear() 두 가지가 있다.

clear()는 ArrayList의 모든 값을 삭제할 때 사용
remove()는 값을 하나씩 제거할 때 사용
remove(Object) / remove(int index)

또한 원하는 값으로 데이터를 삭제를 원하면 아래에서 살펴볼 indexOf() 메소드를 사용할 수 있다. 값이 없다면 -1을 출력한다.

list.remove(2); // 2번 인덱스 삭제 => remove(index)
list.clear(); // 리스트의 모든 값 삭제

list.remove(list.indexOf(2)); // 리스트에 2를 포함한 인덱스 리턴 후 삭제

ArrayList 값 검색

int index = list.indexOf(2); // 원하는 값의 인덱스를 리턴, 없으면 -1 리턴
boolean b = list.contains(2); // 원하는 값의 존재 유무

while(list.indexOf(2) == -1) { // 리스트에 원하는 값 모두 삭제
	list.remove(list.indexOf(2));
}

indexOf(value) 로 원하는 값의 인덱스를 리턴받을 수 있다.
원하는 값의 존재 유무는 contains(value) 를 통해 boolean 값으로 리턴 받는다.
위와 같이 값의 검색을 통해 리스트에 존재하는 원하는 값을 모두 지울 수도 있다.

ArrayList 값 추출, 출력

System.out.println(list); // 리스트 전체 출력
System.out.println(list.get(2)); // 2번 인덱스 출력

for(int i : list) { 
    System.out.println(i);
}

Iterator iter = list.iterator(); // 반복자 사용
while(iter.hasNext()){
    System.out.println(iter.next()); 
}

리스트만 넣게 되면 오버라이딩 된 toString() 메소드에 의해 리스트에 존재하는 모든 데이터들이 한줄로 출력 되고,
get(index) 메소드는 인덱스의 값을 반환해준다.

반복문이나 iterator 를 사용해서 값을 가져올 수도 있다.
ListIterator의 경우, 생성 시 ArrayList의 크기를 입력해주고 역방향으로 출력할 수 있다.

ListIterator<String> listIterator = colors.listIterator(colors.size());
        while (listIterator.hasPrevious()) {
            System.out.print(listIterator.previous() + "  ");
        }

LinkedList

LinkedList란, 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조 라고 한다.

👩?

풀어보자면, LinkedList는 연결된 노드들의 집합인데, 각 노드는 데이터와 포인터(다음 노드를 가리키는) 로 이루어져 있다.
데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. 데이터 추가시 새로운 데이터 노드를 만들고 이전 노트의 포인터를 새 노드를 가리키게 만든다. 즉, 각 노드는 앞 뒤의 노드의 위치를 저장한다.

Java Collection Framework 를 보면 LinkedList 는 AbstractSequentialList를 상속하고 있다.

ArrayList는 데이터들이 순서대로 늘어선 배열의 형식을 취하는 반면에, LinkedList는 자료의 주소값으로 서로 연결되어있는 구조를 하고있다.

ArrayList와 다르게 중간에 데이터가 추가되거나 삭제되어도 앞으로 당겨지거나 뒤로 미는 동작이 없다. 추가나 삭제를 할 경우 변경되는 노드의 앞쪽의 노드의 참조를 변경하기만 하면 된다.

근데 LinkedList는 특정데이터를 인덱스 값을 통해 따라갈 수가 없다. 100번째 노드를 확인하기 위해서는 첫번째부터 100번째 노드까지 참조를 따라서 하나씩 이동해야 확인할 수 있는 것이다. 이때문에 특정 노드까지 따라가는 탐색 성능이 떨어진다.

그래서 주로 ArrayList는 검색이 많은 경우에 사용하고, LinkedList는 잦은 삽입/삭제 시에 사용한다.

LinkedList 종류

앞전에서 단순 연결 리스트(Singly Linked List)는 next로 현재 노드에서 다음 노드로 갈 수 있지만 이전 노드로는 갈 수 없었다. 그래서 데이터 접근성이 좋지 않았는데,

그래서 이걸 보완해서 나온게 이중 연결리스트이다.

서로 근접한 요소를 앞뒤로 연결할 수 있게 나온것인데, 다음요소 이전요소를 저장해서 앞뒤로 이동이 가능하게 하여 접근성을 향상시켰다. 대신 새로운 요소를 추가 삭제 할 시에 두개(앞/뒤)의 연결을 해줘야하니 시간은 좀 더 걸린다.

하지만 아직 데이터를 접근하기 위해서는 하나하나 거쳐 가야 한다.

이걸 또! 개선하기 위해 나온게 원형 이중 연결 리스트 (Circular Doubly Linked List)다

위에서는 양끝의 값이 null 이었다. 이점을 이용해서, 맨뒤의 다음요소를 맨앞, 맨앞 이전요소를 맨뒤와 연결해놓는다.
이렇게 되면 맨 처음에서 끝으로 갈때 원래는 하나씩 노드를 거쳐갔어야 하는데, 이제는 이전요소로 가면 맨끝과 연결된다. tv채널 돌릴때 ch1일때 내리면 ch999가 되는 것처럼..

하지만 아무리 개선을 했어도 배열보다는 접근성이 낮다는 단점을 가지고 있다.

Linkedlist 생성

LinkedList<Integer> list1 = new LinkedList<Integer>(); // 타입 지정
LinkedList<Integer> list2 = new LinkedList<>(); // 타입 생략 가능
LinkedList<Integer> list3 = new LinkedList<>(integers1); // 다른 Collection값으로 초기화
LinkedList<Integer> list4 = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5)); // Arrays.asList()

Set이나 다른 ArrayList 등을 전달해서 해당 값으로 초기화하는 것도 가능하다.
Arrays.asList로 한 번에 여러 개의 값을 입력하면서 초기화시키는 방법도 있다.
ArrayList와 다른 점은 가용량이 의미가 없기 때문에(데이터가 추가될 떄마다 노드들이 생성되어 참조 체인데 추가되는 방식이기 때문에) 가용량을 받는 생성자가 존재하지 않는다는 점이다.

LinkedList 요소 추가/변경

add() 메소드로 엘레멘트를 추가할 수 있고 set() 메소드로 기존에 추가된 값을 변경하는 것 또한 가능하다.

LinkedList<String> animals = new LinkedList<>();
// add() method
animals.add("dog");
animals.add("cat");
animals.add(0, "cow");
animals.add("mouse");

// set() method
animals.set(0, "human");

System.out.println(animals);

[human, dog, cat, mouse]

add() 에 인덱스를 지정하지 않으면 가장 끝에 값이 추가되고 값을 찾아갈 때 처음 부터 순차적으로 찾아간다.

LinkedList 요소 삭제

remove() 메소드로 값을 삭제할 수 있고 값 전체 삭제 하고 싶을 경우 clear()를 사용하면 됨.

list.remove(); // 첫 번째 값 제거
list.remove(3); // 3번째 값 제거
list.removeFirst(); // 첫번째 값 제거
list.lastFirst(); // 마지막 값 제거

list.clear(); // 모든 값 제거

인덱스 값을 준 경우, 해당 노드까지 탐색을 하고 나서 삭제를 하기 때문에 O(n)시간이 소요된다.

LinkedList 전체 값 확인, 값 존재 유무 확인

LinkedList의 전체 값 확인, 값 존재 유무 확인은 ArrayList와 동일하다.

ArrayList, LinkedList 의 차이

정리해보자면 이 둘의 차이는 이렇다.

✅ ArrayList

배열의 크기를 동적으로 할당하고 싶을 때 사용
데이터의 삽입, 삭제 시 임시 배열을 생성해 데이터를 복사하는 방법 사용(비효율적인 메모리사용)

[검색]

인덱스를 활용해 데이터에 빠른 접근 가능 (데이터 읽기에 성능이 빠름)

[삽입 & 삭제]

배열 끝부분을 제외한 위치의 데이터 삽입, 삭제 시 데이터의 복사와 이동이 많이 발생해 시간이 많이 걸림

✅ LinkedList

ArrayList의 단점을 보완하기 위함(크기가 고정, 추가삭제 느림)
데이터의 순서에 따라 노드의 포인터 부분을 이용해 서로 연결한 구조
노드와 포인터로 관리되기 때문에 메모리 측면에서 봤을 때는 ArrayList가 낫다. (데이터가 많을수록 접근성이 떨어짐)