[Java] ArrayList, LinkedList 차이

#1 ArrayList와 LinkedList

Java에서 기본형(int, boolean, String, char) 또는 인스턴스를 리스트로 저장하는데는 보통 배열을 사용한다. 하지만 배열은 선언시에 크기를 정해줘야하므로, 동적으로 요소의 추가나 삭제 등이 불가능하다는데 그 단점이 있다. 만약 배열의 원소를 추가하거나 삭제하려면, 직접 새로운 배열을 선언해주어서 카피하는 식으로 사용해야한다. 지속적으로 데이터를 변경해야되는 알고리즘 문제나, 어떤 프로그램의 구현에서 이는 꽤나 큰 불편함으로 다가온다.

 

이러한 불편함을 해소시켜주는 것이 List 인터페이스를 상속하여 구현된 ArrayList와 LinkedList 클래스이다. 이 둘은 모두 Collections 객체의 일종이다. 이 두 가지 리스트는 동적으로 사용할 수 있어 새로운 값의 추가나 제거가 유용하여 기본 배열의 단점을 커버해준다. 하지만 기본형을 내부 원소로 갖는 것이 아니라 Integer, Character 등의 클래스형 원소를 가져야 하므로, 메모리적인 부분에서 배열보다 더 공간을 차지할 것이라 생각된다.

//일반 배열
int[] Iarr = new int[10];
char[] Carr = new char[10];
String[] Sarr = new String[10];
boolean[] Barr = new boolean[10];

//List 배열
ArrayList<Integer> IarrL = new ArrayList<>();
ArrayList<Character> CarrL = new ArrayList<>();
LinkedList<String> SarrL = new LinkedList<>();
LinkedList<Boolean> BarrL = new LinkedList<>();

 

이 둘은 분명히 비슷하지만, 다른 점을 가지고 있다. 따라서 상황에 따라 다르게 써야한다.

 

#2 ArrayList

ArrayList는 메모리에서 내부적으로 데이터를 배열로 만들어 관리하며, 데이터의 추가, 삭제를 위해 아래와 같이 임시 배열을 생성해 데이터를 복사하는 방법을 사용하고 있다. 

각 데이터 추가 / 삭제마다 배열을 새로 만들어 복사해주므로, 기존 10개에 데이터에 1개를 추가하면 10번의 복사가 요구되는 것이다. 따라서 O(n)의 시간복잡도가 추가/삭제에 요구된다.

반면 참조의 경우에는, 배열의 형태로 데이터들이 저장해 있기 때문에 사용자가 원하는 인덱스의 데이터를 O(1)의 시간에 바로 꺼내올 수 있다. 

따라서 ArrayList의 경우에는 추가/삭제에는 불리하고, 참조에는 유리하다.

 

#3 LinkedList

Linkedlist는 데이터를 하나의 노드로 구성하며, 각 노드는 자신의 이전 노드와 다음 노드만 알고 있다. 시작노드 또한 다음 노드만 가리키고 있을 뿐이다. ArrayList가 전지적인 시점에서 보는 데이터 셋이라면, LinkedList는 1인칭 시점에서 보는 데이터 셋이라고 생각해볼 수 있다.

각각의 노드는 개별적으로 메모리에 저장되고, 다음 노드의 위치를 가르키고 있으므로, 데이터의 추가/삭제 시 나머지 데이터들의 복사가 필요없다. 단지 새로운 데이터 노드를 만들고, 그걸 끼워넣어주기만 하면된다. 따라서 데이터의 추가/삭제에서 O(1)의 시간 복잡도를 가질 수 있다. 

반면에 데이터의 참조 부분에서는, 해당 인덱스에 바로 접근했던 ArrayList와 다르게 원하는 인덱스까지 노드 하나하나를 통과해가며 다음 노드를 체크해야한다. 따라서 최대 O(n)의 시간복잡도가 발생할 수 있다.

결과적으로 LinkedList의 경우에는 추가/삭제에는 유리하고, 참조에는 불리하다.

 

#4 Conclusion

ArrayList는 대량의 데이터에 대하여 추가/삭제에는 불리하고, 참조에는 유리하다. 반면 LinkedList는 대량의 데이터에 대하여 참조에는 불리하고, 추가/삭제에는 유리하다. 따라서 상황에 따라 필요한 것을 사용한다면 프로그램의 성능적인 부분에서 더 좋은 결과를 얻을 수 있을 것 같다.