[JAVA] (Collections ①) ArrayList / LinkedList

 

이번 포스팅에서는 Collection의 List에 대해 알아보자.

 

 

List에는 LinkedList와 ArrayList가 있는데, 먼저 두 List의 구조를 보면 아래와 같다.

 

 

1. ArrayList 

 : n개의 자료를 저장할 때 자료들을 하나의 연속적인 묶음으로 묶어 저장하는 구조.

=> 위의 구조에서 "20"과 "30" 사이에 "10"이라는 값을 삽입하려면

     먼저 삽입할 값의 위치를 기준으로 그 뒤의 자료들이 모두 뒤로 이동하는 연산을 수행한 뒤

     삽입할 위치에 값을 삽입한다.

add

addAll

 

=> 중간의 자료 하나를 삭제하려면

      삭제할 자료가 위치한 인덱스의 자료를 삭제한 뒤

      삭제한 자료의 위치를 기준으로 그 이후 자료들을 앞으로 땡기는 연산을 수행한 뒤

      List의 맨 마지막은 비어있는 상태로 완료한다. (메모리가 낭비될 수 있음)

 

remove

 

* 특징

 - 사이즈가 고정되어 있음

 - 자료를 추가로 삽입할 경우 사이즈를 늘려주는 연산을 추가해야함

 - 무작위 접근 가능

 - (순차적인 인덱스로 인해) 삭제 시, 삭제된 빈 인덱스를 채워야 하기 때문에 연산이 추가됨

 - 삭제되는 공간만큼 낭비되는 메모리가 많음

 - 삽입/삭제가 빈번하게 발생하는 프로세스에는 적절하지 않음

 

 

2. LinkedList 

 : ArrayList와는 다르게 자료와 자료간의 연결(link)을 이용하여 list를 구현한 것.

=> LinkedList의 삽입은 추가될 자료의 node를 생성한 뒤

     추가될 자료의 인덱스 이전 node와 추가될 이후 node를 연결해준다.

=> 삭제 시에는 삭제할 노드의 이전 노드와 이후 노드를 연결해준다.

* 특징

- ArrayList처럼 뒤로 밀거나 땡기는 연산없이 주소만 서로 연결시켜주면 되기 대문에 삽입/삭제가 빠르고 쉬움

- 삽입/삭제가 빈번하게 발생하는 프로세스에 적절함

- 순차접근만 가능

- n개의 자료 저장 시 LinkedList는 자료들을 저장공간에 불연속적인 단위로 저장 -> 노드 접근하는데에 상대적으로 긴 시간 소요

- LinkedList는 참조자를 위해 추가 메모리 할당이 필요함 

출처: 위키백과

 

* 종류

- 단일 연결 리스트 : 각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킨다.

- 이중 연결 리스트: 단일 연결 리스트와 비슷하지만 포인터 공간이 두개 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

- 원형 연결 리스트: 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.