[DataStructure] Array, List와 Array List, Linked List

배열(Array)

• 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조 이다.
• 배열의 값은 인덱스를 통해 참조할 수 있으며, 선언한 자료형의 값만 저장할 수 있다.
• 배열은 동적으로 값을 삽입하거나 삭제하려면 본래의 값들을 이동시켜야 하는 과정이 필요해서 시간이 소요된다.

리스트(List)

• 리스트는 값과 포인터를 묶은 로드라는 것을 포인터로 연결한 자료구조이다.
• 리스트는 인덱스가 없으므로, 값에 접근하기 위해 Head 포인터에서 순서대로 접근해야 한다.
• 접근 시간은 느리지만, 데이터 삽입과 삭제 연산 속도는 빠르다.
• ADT(Abstract Data Type)에서 List는 순서가 있고 중복을 허용하는, 값들을 저장하는 추상 자료형으로 사용된다.
• Set이나 Map을 사용하는게 더 적절한 상황이 아니라면 거의 모든 상황에서 리스트를 사용한다.
• ArrayList나 LinkedList가 대표적인 리스트 구현체이다.

이미지 출처: https://assets-global.website-files.com/63e3d6905bacd6855fa38c1c/63e3d6905bacd66654a39004_THUMB_%20ArrayList%20vs%20LinkedList-min.jpg

Array List

• 배열(Array)을 사용하여 List를 구현한 자료 구조이다.
• Array List는 연속적인 메모리 공간에 데이터 저장한다.
• 따라서 CPU 캐시 활용 측면에서 성능 측면에 이득이 있다.
• insert를 할 때 데이터 시프트로 공간을 확보하는 과정을 거친다.
• 데이터 추가를 할 때 공간 부족 시 더 큰 배열 생성하고 값을 Copy하는 과정을 거친다.
• 함수 실행으로 인덱스 값 가져오며, 더 이상 사용하지 않는 값은 새 배열로 이동.

Linked List

• Linked List는 연결된 노드들로 구성되며, 각 노드는 값과 다음 노드를 가리키는 포인터를 저장한다.
• 노드들은 서로 연결되어 있어 한 노드가 다음 노드를 가리키고, 리스트의 끝은 '널'값을 갖는다.
• header는 리스트의 맨 처음을, tail은 리스트의 마지막 노드를 가리키는 레퍼런스이다.
• Linked List는 띄엄띄엄 메모리에 저장된다.

Circular linked list, Doubly linked list, circluar doubly linked list

Circular linked list

• 맨 끝의 노드(tail)이 다음 노드로 맨 처음 노드(head)를 가르키는 Linked List이다.

Doubly linked list

• 양방향으로 움직일 수 있는 linked list
• 자유롭게 노드 이동 가능하며, 빠르게 접근할 수 있는 장점이 있음.

Circular doubly linked list

• 양방향으로 움직일 수 있는 Circular linked list

Linked List vs Array List 성능 비교

기능	ArrayList	LinkedList
데이터 저장 방식	연속된 메모리 공간에 데이터 저장	독립적인 노드(node)로 데이터 저장, 각 노드는 데이터와 다음 노드를 가리키는 포인터(pointer)를 갖음
삽입/삭제 (중간)	느림 (데이터 이동 필요)	빠름 (연결만 변경)
삽입/삭제 (끝)	빠름 (배열 끝에 추가/삭제)	빠름 (헤드/테일 노드 연결 변경)
탐색	빠름 (인덱스 접근 가능)	느림 (탐색 위해 순차적으로 노드 이동)

그냥 Array List를 쓰세요

Java의 LinkedList를 구현한 Josh Bloch는 X(트위터)에 "LinkedList 실제로 쓰는 사람 있어? 난 내가 구현했지만 한 번도 안 써봤어." 라는 글을 작성했다고 한다.

배열 확장이 필요한 경우 새로운 배열에 복사하는 추가 시간 발생과 Array List의 삽입/삭제 시 데이터 시프트 시간 비용?

Java의 Array List는 위와 같은 문제를 해결하기 위해 계속해서 튜닝하고 최적화가 되고 있다고 한다.

FIFO 구현? ArrayDeque가 더 좋아

ArrayDeque는 Deque 인터페이스를 구현한 resizable array이다. 이 자료구조는 효율적인 데이터의 삽입/삭제를 가능하게 해준다.

참고

• https://youtu.be/xvi-n11kym0?si=xipFgxfzpviAOLhk