[JAVA] List - ArrayList, LinkedList
1. ArrayList
ArrayList 는 기존의 Vector 를 개선한 것으로 Vector 의 구현원리와 기능적인 측면이 동일하다.
ArrayList 는 List 인터페이스를 구현한 클래스이기 때문에 저장된 값의 순서를 유지하고 중복을 허용한다. ArrayList 는 Object 배열을 이용하여 데이터를 순차적으로 저장한다. 입력되는 객체들은 배열에 순서대로 저장되며, 배열의 길이를 넘어가면 더 큰 배열을 새로 생성하여 기존의 값들을 복사한 다음에 값을 저장한다. 값을 삭제하면 삭제된 값의 공간이 빈다. 그러면 나머지 값들이 자리이동을 진행하여 빈 공간을 채운다.
ArrayList 나 Vector 와 같이 배열을 이용하여 데이터를 저장하는 자료구조는 인덱스를 사용해 값을 읽어오고 저장하는 작업에는 효율이 좋지만, 배열의 크기를 넘어가는 값의 저장에는 항상 resize 작업이 필요하기 때문에 이를 잘 고려하여 사용하여야 한다.
2. LinkedList
배열을 사용하는 ArrayList 와 같은 자료구조는 사용하기 쉽고 데이터의 조회의 효율이 좋다. 하지만 다음의 단점을 가지고 있다.
1) 크기를 변경할 수 없다.
배열의 크기를 변경할 수 없기 때문에 크기를 넘어가는 경우 새로운 배열을 생성하여 값을 복사하여야 한다.
이러한 작업을 줄이기 위해서는 충분히 큰 크기의 배열을 생성해야 하기 때문에 메모리 문제가 발생할 수 있다.
2) 비순차적인 데이터의 추가, 삭제에 대한 시간이 많이 걸린다.
배열의 순서에 따라 제일 마지막에 값을 추가 삭제하는 것은 쉽지만 배열의 중간에 값을 추가 삭제하는 경우는 효율이 좋지 않다. 변경이 있는 값외에 나머지 값들이 자리이동을 수행해야 하기 때문이다.
위의 단점을 보완하기 위해 만들어진 자료구조가 Linkedlist 이다. Linkedlist 는 객체가 배열에 저장되는 것이 아니라 각 객체들이 자신 다음에 오는 객체를 알고 있어서 체인과 같이 연결되어 있는 구조로 데이터를 저장한다.
Linkedlist 에서 데이터의 추가, 삭제는 간단하다. 데이터를 추가 또는 삭제하려는 위치의 양 옆의 데이터들과 연결만 수정해주면 된다. 만약 i 번째에 데이터를 추가하려는 경우 i - 1 번쨰 데이터의 다음 데이터로 새로운 데이터를 연결해주고, 새로운 데이터의 다음 데이터로 기존의 i 번째 데이터를 연결해주면 된다. 반대로 i번째 데이터를 삭제하는 경우 i - 1 번째 데이터의 다음 데이터를 i 번째에서 i + 1 번째로 변경해주면 된다.
일반적인 Linkedlist 는 다음 데이터에 대한 연결정보만 가지고 있기 떄문에 이전 데이터에 대한 접근이 어렵다. 이런 단점을 해결하기 위해서 나온 것이 doubley linked list 이다. 이중 연결 리스트는 다음 데이터 뿐만 아니라 이전 데이터가 무엇인지도 저장하여 앞뒤의 연결을 통해 데이터 접근을 할 수 있도록 한다.
- ArrayList vs Linkedlist
1) 순차적으로 데이터를 추가, 삭제하는 경우 ArrayList 가 Linkedlist 보다 빠르다.
데이터의 개수가 배열의 크기를 넘어가지 않는 경우에는 ArrayList 의 마지막 위치에 데이터를 저장하고 삭제하면 되기 때문에 따로 link 연결 작업을 수행하지 않아도 되는 ArrayList 가 보다 빠르다.
2) 중간에 위치한 데이터를 추가, 삭제하는 경우 Linkedlist 가 ArrayList 보다 빠르다.
중간에 위치한 데이터를 추가, 삭제하는 경우 ArrayList 는 나머지 데이터들의 자리이동을 수행해야 한다. 하지만 Linkedlist 의 경우에는 간단히 주변 데이터의 연결 관계만 수정해주면 되기 때문에 Linkedlist 가 효율이 더 좋다.
3) 인덱스를 이용하여 데이터의 조회하는 경우 ArrayList 가 Linkedlist 보다 빠르다.
ArrayList 는 배열을 사용하여 데이터를 저장하기 때문에 인덱스를 사용하여 데이터에 바로 접근할 수 있다. 하지만 Linkedlist 의 경우 인덱스를 사용하지 않기 때문에 매번 첫번째 노드부터 i 번째 데이터까지 찾아가야해서 비효율적이다.