ArrayList & LinkedList

주제

• ArrayList와 LinkedLikst를 비교하며 알아봅시다.

내용

🦋 ArrayList

• 내부적으로 데이터를 배열에서 관리한다.

• 배열과 다른 부분은 생성할 때 크기를 고정하지 않아도 동적으로 늘어난다. (초기 용량은 10)

• 각 데이터는 인덱스를 가지고 있어 한 번에 참조가 가능하다.

🌟 LinkedList

• 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. -위키백과

• 노드의 자료 주소 값을 통해 연결되어 있는 구조

• 논리적 저장 순서와 물리적 저장 순서가 일치하지 않는다.

• 트리의 근간이 되는 자료구조

Random Access Data Structure (비순차적 자료구조)

• 다른 자료에 의지하지 않고 접근 할 수 있는 방법

• 책 목차의 페이지를 보고 원하는 페이지로 바로 갈 수 있는 예시

• Array, ArrayList

Sequential Access Data Structure (순차적 자료구조)

• 다른 자료에 의지하며 접근하는 방법

• 다른 element를 거치지 않고는 접근을 할 수 없는 구조

• 지하철은 다른 노선들을 거쳐야만 도착 할 수 있는 예시

• Stack, Queue, LinkedList

접근방법

• ArraysList
• Random Access Data Structure : 자료에 비순차적으로 접근한다.
• O(1)

• LinkedList
• Sequential Access : 자료에 접근할 때 순차적으로 검색하면서 찾는다.
• O(n)

저장 방식

• Arrays List
• 메모리에 연이어 저장된다.

• LinkedList
• 새로운 요소는 메모리 어딘가에 저장된다.
• 새로운 요소에 할당된 메모리 위치 주소는 이전 노드에 저장된다.

삽입과 삭제

• ArrayList
• 용량에 벗어나는 경우 새로운 배열을 만들어 복사한다.
• 그래서 초기용량을 예측하기 쉽지 않지만 대략적으로라도 생각해보고 설정하는 것이 좋다.
• 삭제의 경우 중간이나 처음의 원소를 삭제한다면 빈 공간을 다시 채워야 하는 과정이 필요하기 때문에 비효율적입니다.

• LinkedList
• 새로운 요소는 빈 메모리 위치에 저장되고, 이전 노드에 메모리 위치 주소를 변경해준다. O(1)
• 원하는 위치 접근 후 삽입 삭제시 원소를 찾기 위해서 O(n)의 시간이 추가적으로 발생
 

결론

• 순차적 추가/삭제의 경우 ArrayList가 LinkedList보다 빠르다.
• 조회가 빈번하다면 ArrayList

• 중간 데이터를 추가/삭제 하는 경우에는 LinkedList가 ArrayList보다 빠르다.
• 삽입 삭제가 빈번하다면 LinkedList

• 공간 복잡도는 ArrayList가 유리하다.
• LinkedList는 노드와 포인터로 관리된다.
• prev, next를 유지하는 포인터라는 오버헤드가 발생하게 된다.