LinkedList와 ArrayList

LinkedList

• ArrayList 삽입 과정
  1) List의 크기를 삽입될 자료만큼 늘리는 연산을 수행한다.
  2) 삽입될 자료의 위치를 기준으로 기존 데이터들을 뒤로 혹은 앞으로 이동하는 연산을 수행한다.
  3) 해당 위치에 자료를 입력한 후 삽입연산을 마친다.

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

<장점>

• 몇 개의 참조자만 바꾸어 새로운 자료의 삽입이나 기존 자료의 삭제를 위치 상관 없이 빠른 시간안에 수행할 수 있다.
• 메모리 용량이 무한정하다고 가정할 때 무한개수의 자료를 삽입할 수 있다.

<단점>

• 단순 LinkedList의 경우 단방향성을 가지고 있기 때문에 순차접근만 가능하다. (인덱스를 이용한 자료 탐색에는 적합하지 않다.)
• 참조자를 위해 추가적인 메모리를 할당해야 한다. 자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가적인 메모리할당은 비실용적일 수 있다.

삽입과 삭제 시 부가적인 연산이 필요하다. 이는 시스템의 성능 저하로 이어져, 수정이 빈번하게 발생하는 프로세스의 경우 치명적인 단점이 된다. 또한 삭제하는 과정에서 그 공간만큼 메모리 낭비가 많아지게 된다.

---

ArrayList

• LinkedList 삽입 과정
  1) 추가될 자료의 node를 생성한다.
  2) 추가될 자료의 '해당 인덱스 이전의 node'의 '다음 node'를 추가될 node로 설정한다.
  3) 추가될 node의 다음 node를 인덱스 이전 node의 다음 node로 설정한다.

• LinkedList 삭제 과정
  1) '삭제할 노드의 이전 노드'의 다음 노드를 '삭제할 노드의 다음 노드'로 설정한다.

<장점>

• 자료들을 하나의 연속적인 묶음으로 묶어 저장하기 때문에 무작위 접근이 가능하다.

<단점>

• 크기가 한정되어 있으며 크기를 재정하는 연산이 굉장히 많지만 까다롭다.
• 시간복잡도가 O(N)만큼의 연산 속도가 걸리기 때문에 자료의 최대 개수에 영향을 받는다.

연결 형태로 이루어져 부가적인 연산 없이 주소만 서로 연결 시켜주면 되기 때문에 삽입 및 삭제가 ArrayList보다 빠르고 용이하다.

---

시간복잡도 비교

참고자료