ArrayList와 LinkedList

ArrayList

• 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 일반 배열과 비슷
• 하지만 ArrayList는 배열과 다르게 배열을 추가하고 삭제하는 메서드가 존재
• 데이터 추가시 더 큰 용량의 임시 배열을 만들어 복사

LinkedList

• 연결된 노드들의 집합인데, 각 노드는 데이터와 포인터(다음 노드를 가리키는) 로 이루어져 있다.
• 데이터 추가시 새로운 데이터 노드를 만들고 이전 노트의 포인터를 새 노드를 가리키게 만든다
• 즉, 각 노드는 앞 뒤의 노드의 위치를 저장한다.

ArrayList 메서드

ArrayList에서 배열을 삽입/삭제할 때 사용하는 메서드

삽입

1. List의 크기를 삽입될 자료의 크기만큼 늘리는 연산을 수행한다.
2. 삽입될 자료의 위치를 기준으로 기존의 자료들으르 한 칸 씩 뒤로 혹은 앞으로 이동하는 연산을 수행한다.
3. 해당 위치에 자료를 삽입한 뒤 연산을 종료한다.

삭제

1. 삭제될 자료가 위치한 인덱스의 자료를 삭제한다.
2. 삭제한 자료의 인덱스를 기준으로 이후의 자료들을 이동하는 연산을 수행한다.
3. List의 마지막은 비어있는 상태로 삭제를 완료한다.

LinkedList 메서드

LinkedList에서 배열을 삽입/삭제할 때 사용하는 메서드

삽입

1. 추가될 자료의 node를 생성
2. 추가될 자료의 해당 인덱스 이전의 node의 다음 node를 추가될 node로 설정
   1. 33의 다음 node를 추가될 자료의 node로 설정
3. 추가될 node의 다음 node를 인덱스 이전 node의 다음 node로 설정
   1. 추가될 node인 BB의 다음 node를 인덱스 이전 node인 33의 다음 node인 AA로 설정
   2. BB의 다음 node로 AA 연결

삭제

1. 삭제할 node[33]의 이전 node[66]의 다음 node를 삭제할 node[33]의 다음 node[AA]로 설정

ArrayList와 비교한 LinkedList의 장단점

장점

• 자료의 삽입과 삭제가 용이하다
• 리스트 내에서 자료의 이동이 필요하지 않다
• 사용 후 기억 장소의 재사용이 가능하다
• 연속적인 기억 장소의 할당이 필요하지 않다

단점

• 포인터의 사용으로 인해 저장공간의 낭비가 있다
• 알고리즘이 복잡하다
• 특정 자료의 탐색 시간이 오래 걸린다

ArrayList와 LinkedList의 비교 성능

	ArrayList	LinkedList
Index	O(1)	O(n)
Insert/Delete at Beginning	O(n)	O(1)
Insert/Delete at End	O(1)	O(n) - last element is unknown, O(1) - last element is known
Insert/Delete in middle	O(n)	search time + O(1)
Wasted Space(Average)	O(n)	O(n)

참고자료

https://www.nextree.co.kr/p6506/