ArrayList, LinkedList

ArrayList와 LinkedList 둘 다 자바에서 제공하는 List 인터페이스의 구현체이다.

ArrayList

• 내부적으로 배열을 사용하며 메모리 상에 연속적으로 위치한다.
• 배열(Array)과의 차이점은 다음과 같다.
  • 자바를 기준으로, 기본 타입만 저장할 수 있는 Array와 달리 ArrayLists는 Object도 저장할 수 있다. ArrayList에 add를 통해 기본 타입의 데이터를 추가하면 오토 박싱이 사용된다.
  • Array는 초기 사이즈가 고정되어 있고 변경이 불가하다. 반면 ArrayList는 이 또한 배열이기 때문에 초기 사이즈가 변경 불가한 것은 Array와 같지만, 사이즈가 가득 차면 내부적으로 새로운 메모리 공간을 할당받아(기존 용량의 1.5배) 새로운 배열로 데이터를 옮긴다.
• 배열의 사이즈가 가득 차면 내부적으로 새로운 배열을 생성하고 데이터가 옮겨진다.
  • default 초기용량은 10이다.
  • 용량이 꽉차면 oldCapacity + oldCapacity / 2로 용량을 늘린다. (예를 들어 oldCapacity가 8이면 12로 늘린다.)
• 데이터 조회: 인덱스를 통해 데이터에 접근하므로 O(1)의 시간 복잡도를 갖는다. 이를 Random Access라고 한다.
• 데이터 삽입/삭제: 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 중간에 데이터를 추가하려면 빈자리를 만들기 위해 다른 데이터들을 옮겨야 하고, 중간 데이터를 삭제하면 빈 공간을 없애기 위해서 데이터들을 옮겨야 한다. 따라서 데이터가 많은 경우 매우 비효율적이다. (시간 복잡도: O(N))

LinkedList

• 메모리 상에 연속적으로 위치하지 않고 각각의 노드가 흩어져 있다. 
• 각 노드는 자신과 연결된 다음 요소에 대한 참조값과 데이터로 구성되어 있다.
• head는 첫 번째 노드를 가리키는 노드이고, tail은 마지막 노드를 가리키는 노드이다.
• 데이터 조회: 특정 원소에 접근하기 위해 head나 tail이 가리키는 노드부터 순차적으로 조회하기 때문에 오래 걸린다. (시간 복잡도: O(N))
• 데이터 삽입/삭제: 데이터를 삽입하고 삭제하는 것은 빠르지만, 삽입/삭제할 위치를 찾기 위해 head나 tail이 가리키는 노드부터 순차적으로 조회하기 때문에 오래 걸린다. 
  • 그럼에도 ArrayList보다 빠른 성능을 갖는다. ArrayList는 데이터를 삽입하다가 공간이 꽉 차면 내부에서 새로운 메모리 공간을 할당받아 데이터를 옮기는 작업이 일어나도, 데이터 삭제시에도 중간에 빈 공간이 있으면 안되기 때문에 빈 공간을 메꾸기 위해 데이터를 옮기는 작업이 일어난다.
  • 그러나 LinkedList는 데이터를 추가할 때 동적으로 메모리 공간을 할당받아서 새로운 데이터를 생성하고, 추가하고자 하는 위치의 이전 노드가 추가할 요소를 참조하고, 추가할 요소가 다음 노드를 참조하도록 변경하면 된다. 그리고 데이터 삭제 시에도 삭제할 노드만 찾으면 그 이전 노드가 삭제할 노드의 다음 노드를 참조하도록 변경하면 되므로 처리 속도가 빠르다.
• Singly LinkedList: 이동방향이 단방향이다. 각 노드는 데이터와 그 다음 노드를 가리키는 포인터로 구성된다.

• Doubly LinkedList: Singly LinkedList는 이동 방향이 단방향이기 때문에 이전요소에 대한 접근이 어려운데,이를 보완하여 양방향 이동이 가능하다.각 노드는 데이터와 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터로 구성된다. (LinkedList 클래스가 구현된 형태이다.)

• Doubly Circular LinkedList: Doubly LinkedList의 첫 번째 요소와 마지막 요소를 서로 연결시킨 것이다. 즉 마지막 요소의 다음 요소가 첫 번째 요소가 되고, 첫 번째 요소의 이전 요소가 마지막 요소가 된다.