[JAVA]List

배열(Array)

: 동일한 타입의 여러 원소를 선형 집합으로 관리하는 정적 데이터 구조

• 생성과 동시에 크기가 고정되어 늘릴 수 없다.
• 메모리상에 일렬로 저장되어 Random Access가 가능하다.
• 원소에 접근과 변경은 빠름, 중간에 원소 추가&삭제시 원소를 옮겨야 하므로 오래걸림.. 
• get, add : O(1)
• insert, remove : O(N)

 

리스트(List)

: 동일한 타입의 여러 원소를 선형 집합으로 관리하는 동적 데이터 구조

• 원소가 추가&삭제됨에 따라 크기가 변경될 수 있다.
• List Interface 구현체에 따라 특성이 다르다.
• ArrayList, LinkedList, Vector 가 있음

---

 

ArrayList

: 동적 배열을 사용한 List 구현체

원소가 추가될 때 배열에 남은 공간이 없다면, 크기를 일정 배수로 늘려 기존 원소를 옮긴다.

배열과 비슷한 성질을 가짐 -> 지정한 위치의 원소 접근이 빠름(O(1)), 중간 원소 삽입/제거는 원소를 옮겨야 하므로 느림

 

• add(E e) -> O(1)
  • 마지막 위치에 e를 추가한다.
  • 배열이 꽉 차면 배열을 늘린 후 추가한다.(growCapacity 실행), 늘리고 추가할때는 O(N)만큼의 시간복잡도가 걸리지만.. 많이 발생하지 않아서 add는 평균적으로 O(1) 만큼의 시간복잡도를 가진다.
  • *growCapacity: x배의 배열을 생성한 후, copy를 한다. 그리고 남은 자리에 새로운 값을 넣는다. 보통 1.5배.. Vector는 2배라고 함.. -> O(N)

 

• get(int idx) -> O(1)
  • idx의 값 접근 

 

• insert(int idx, E e) -> O(N)
  • 삽입할 위치 뒤에 값들을 전부 오른쪽으로 한 칸씩 옮기고 e를 삽입해준다.
  • 만약 배열 크기가 작은 경우, growCapacity를 실행한 후 삽입한다.

 

• remove(int idx) -> O(N)
  • 삭제할 위치 뒤에 값들을 전부 왼쪽으로 한 칸씩 옮긴다.

 

 

 

LinkedList

: 차례로 연결된  Node를 사용한 구현체

원소가 추가/삭제될 때마다 해당 원소의  Node가 추가/삭제된다.

지정된 위치의 원소에 접근하기 위해 선형 탐색(처음부터..)이 필요하다.

순차적인 접근시 Iterator를 사용해 효율적으로 관리할 수 있다.

중간 원소 삽입/제거는 Node의 연결을 갱신하는 것이므로 다른 Node에 영향을 끼치지 않음

 

LinkedList는 Node들의 연결로 이루어져 있다. Node는 E item, 다음을 가리키는 next를 가진다. LinkedList는 제일 처음 시작하는 Node인 firstNode, 마지막 Node인 lastNode, 크기인 size를 포함한다.

 

• addLast(E e) -> O(1)
  • e를 가지는 new Node를 생성한다. new Node는 Null을 가리킨다. 
  • 사이즈가 0일때 == 첫 번째로 노드 추가일때 -> firstNode가 NewNode이다. 아닐때는 기존 lastNode 에 new Node를 연결하고 new Node를 lastNode로 지정한다.
  • 모든 과정이 끝나고 사이즈를 증가시킨다.

 

• addFirst(E e) -> O(1)
  • e를 가지는 new Node를 생성한다. new Node는 기존의 firstNode를 가리킨다.
  • 늘 처음에 추가하므로 fitstNode == new Node 로 지정해주면 끝이다. 사이즈를 증가시킨다.

 

• get(int idx) -> O(N)
  • 특정 노드가 앞에서부터 몇 번째인지 모르므로 idx번 반복문을 돌린다.

 

• insert(int idx, E e) -> O(N)
• insert(Node<E> prevNode, E e) -> O(1)
  • idx 사용은 idx번째 노드를 찾아가서 링크를 갱신해야하므로 O(N)
  • 이전 노드(prevNode)사용은 링크를 바로 갱신할 수 있으므로 O(1)

 

• remove(int idx) -> O(N)
• remove(Node prevNode) -> O(1)
• remove(node) -> O(N)
  • idx 사용은 idx번째 노드를 찾아가서 링크를 갱신해야하므로 O(N)
  • 이전 노드(prevNode)사용은 다음 노드를 삭제하는 것이므로 이전노드에 다다음노드(삭제할 노드가 가리키는 == 삭제할 노드의 다음 노드)를 연결 O(1)
  • 삭제할 노드를 주면 이전 노드를 찾아야 하므로 선형탐색을 함 O(N), 이전 노드가 삭제할 노드의 다음 노드를 가리켜야 함.

 

fast campus의 강의에서 발췌함