ArrayList & LinkedList

List는 Set이나 Map을 사용하는게 더 적절한 상황이 아니라면, 거의 대부분 List를 사용한다. List는 순서를 보장하며, 데이터 중복, 추가, 삭제가 자유롭다.

ArrayList

ArrayList는 배열을 사용하여 연속적인 메모리 공간에 순차적으로 데이터를 저장한다.
indexing이 가능하다는 장점이 존재하고, 데이터가 많아도 인덱스로 접근하기 때문에 인덱스 접근은 O(1)을 나타낸다.

ArrayList는 추가,변경 시 데이터 시프트가 발생하면 소모되는 시간이 길다.

LinkedList

비연속적인, 비순차적인 메모리 공간에 데이터를 저장하지만, 순서가 보장된다.
데이터가 많을수록 데이터 탐색에 많은 시간이 소모된다. 즉, node에 의해 가리키는 순서대로 탐색하기 때문에 인덱스에 대한 접근은 O(N)을 나타낸다.

LinkedList는 는 추가,변경 시 데이터 시프트가 발생하면 소모되는 시간이 짧다.

Circular Linked List

종단에 위치한 tail(node)가 head(node)를 가리킨다.

Doubly Linked List

각 node들은 양방향으로 node를 가리키며 탐색에 이점이 있다.

Circular Doubly Linked List

head(node)와 tail(node)는 서로를 가리키며, 각node들은 양방향을 가리킨다.

사용

프로그래밍 특성에 따라 적절한 자료구조를 선택해야한다.

ArrayList

사이즈가 고정적이고 변경사항이 적으며 고정된 인덱스에 계속해서 접근해야 할때

LinkedList

사이즈가 가변적이고 변경사항이 많으면 이점이 있다.

출처 : 쉬운코드 유튜브