[Java][Android] ArrayList와 LinkedList 차이

안녕하세요, 

오늘은 ArrayList와 LinkedList 차이에 대해 알아보겠습니다. 

 

먼저, LinkedList 는 데이터 구조의 한 형태로, 노드가 체인처럼 연결되어 있는 자료구조입니다. 

각 노드는 데이터를 저장하고, 다른 노드와의 연결 정보를 가지고 있습니다. 

 

- 노드(Node) : 데이터와 연결 정보를 담고 있는 구조체, LinkedList의 기본 단위

- 노드의 구성요소

  1. 데이터: 저장된 값

  2. 다음 노드에 대한 참조(주소)

 

LinkedList의 기본 구조 : [HEAD] -> [Node1: Data | Next] -> [Node2: Data | Next] -> [TAIL]

 

 

LinkedList 와 ArrayList의 차이는 아래와 같습니다. 

 

특징	ArrayList	LinkedList
구조	동적 배열 기반	노드 기반
삽입/삭제 속도	느림 (요소 이동 필요)	빠름 (링크만 변경)
검색 속도	빠름 (인덱스로 직접 접근)	느림 (첫 노드부터 순차 검색)

 

LinkedList는 삽입/삭제가 빈번한 경우 효율적입니다.

ArrayList와 달리 요소의 추가와 삭제 시 요소를 이동시키지 않고 참조 주소만 조정하기 때문에 성능 면에서 유리합니다.

 

 

 

 

<LinkedList 의 데이터 삽입 예시>

 

기존 LinkedList 

    [Head] --> [Node1: Data1 | Next -> Node2] --> [Node2: Data2 | Next -> Node3] --> [Node3: Data3 | Next -> null]

 

Node2와 Node3 사이에 Node4를 삽입하는 경우

  - 새로운 노드 생성

  - Node2의 Next (다음 노드 참조 주소)를 Node4 로 변경

  - Node4의 Next( 다음 노드 참조 주소)를 Node3으로 설정

 

삽입 후 LinkedList 

[Head] --> [Node1: Data1 | Next -> Node2] --> [Node2: Data2 | Next -> Node4] --> [Node4: Data4 | Next -> Node3] --> [Node3: Data3 | Next -> null]

 > 주소만 조정되며 나머지 노드는 이동하지 않습니다.

 

 

<ArrayList 의 데이터 삽입 예시>

 

ArrayList는 배열 기반이므로 중간에 요소를 삽입할 경우, 기존 요소를 이동해야 합니다.

 

기존 ArrayList 

Index :         0         1           2
              [Data1]  [Data2]  [Data3]

 

Index 1 위치에 Data4를 삽입하는 경우

1. 기존 데이터 Data2, Data3을 한 칸씩 오른쪽으로 이동
2. Index 1에 Data4를 삽입

 

삽입 후 ArrayList 

Index :         0         1           2          4
              [Data1] [Data4] [Data2]  [Data3]

> 삽입 위치 이후의 모든 데이터가 이동되므로 성능에 영향을 미칩니다.

 

비교항목	ArrayList	LinkedList
삽입방식	삽입 위치 이후의 데이터를 모두 이동	참조 주소만 변경
삽입속	느림 (데이터 이동 필요)	빠름 (특히 중간 삽입 시)