Java로 자료구조 이해하기 2편(Arraylist와 LinkedList)

1편에서는 Array와 ArrayList에 대해서 알아 보았습니다. 2편에서는 LinkedList와 ArrayList를 비교하며 알아보도록 하겠습니다.

LinkedList와 ArrayList는 뭐가 다르지?

대부분 같다고 보면 되고, 핵심적으로 다른 부분은 주소가 순차적이냐 순차적이지 않느냐의 차이입니다. ArrayList는 순차적인 주소를 가집니다 그렇기 때문에 접근성은 정말 빠릅니다. 하지만 중간에 추가 및 삭제 시 느린 자료구조입니다. 이를 개선한 것이 LinkedList 입니다. LinkedList는 배열과는 다르게 Link 즉, 선으로 각 메모리를 연결한 것 입니다. 그래서 접근성은 느리지만, 중간에 추가 삭제는 ArrayList 보다 훨씬 빠릅니다. 그럼 그림으로 알아 보도록 하겠습니다.

그림과 같이 LinkedList는 선으로 연결 되어 있습니다.
그림에 빨간색은 현재 나의 주소 이며, 밑에는 다음 요소의 주소 입니다. LinkedList는 이와 같이 다음 요소의 주소를 가지고 있습니다.
하지만 연속된 주소가 아닐 수 있습니다. 그림은 연속된 것으로 하였습니다. 의미없는 값 입니다.
즉, 불연속적인 주소에 접근하기 위해 선으로 연결하여 접근할 때 하나 씩 접근하게 됩니다. 그래서 접근성이 좋지 않습니다.
하지만 중간에 추가 및 삭제할 때는 선으로 연결이 되어있기 때문에 공간을 밀거나 당길 필요가 없이 선만 다른 다음 요소에 연결 해주면 됩니다.
그렇기 때문에 ArrayList 보다 빠를 수 있습니다. 하지만 끝에 추가 및 삭제는 접근성 자체가 좋지 않기 때문에 ArrayList가 더 빠릅니다.

차이점 정리

1. 순차적으로 데이터 추가/삭제(매번 끝에 추가/삭제하는 것과 같습니다.)
2. -> ArrayList가 빠름
3. 비순차적 데이터 추가/삭제(중간에 추가/삭제하는 것과 같음)
4. -> LinkedList가 빠름
5. 접근성
6. -> ArrayList가 빠름

ArrayList는 배열 기반의 자료구조.
LinkedList는 연결 기반의 자료구조.
ArrayList는 메모리를 미리 만들어 놔야 하므로 남는 공간이 존재할 수 있고, LinkedList는 필요할 때만 한개 씩 생성하기 때문에 효율적으로 사용이 가능.

List의 구현체들

List에는 Vector, ArrayList, LinkedList가 있습니다.
근데 Vector는 무엇일까요?
저도 잘 모르기에 간단하게만 알고 넘어 가겠습니다. Vector는 ArrayList의 옛 버전 입니다.
차이점은 동기화 유무 이며, Vector는 동기화를 지원하여, Thread Safe하고 ArrayList는 반대 입니다.
Thread Safe하다는 의미는 여러 개의 Thread가 들어와도, 한 개의 Thread가 소멸될 때 까지 다른 Thread는 대기해야 한다는 것입니다.
Vector는 Collection 프레임 워크가 나오기 전인 레거시이며, 사용할 일이 없다고 알고 있고, 굳이 지금 알 필요는 없는 부분 같습니다. 이상!