ArrayList & LinkedList 설명과 비교

ArrayList 란? 

---

ㄴ 데이터를 추가하는데로 사이즈가 늘어나는 자료구조 

ㄴ 기본적으로 자바에서 제공되는 Array 의 경우에는 객체 생성시 배열의 크기를 지정해주어야한다. 

ㄴ ArrayList 를 이용하면 데이터를 추가하는데로 사이즈가 늘어나 크기를 지정해주지 않고도 사용가능하다. 

 

 

 

ArrayList 특징

---

ArrayList 는 배열 방이 다 차면, 배열의 크기를 2배로 늘려준다. 

현재 배열보다 2배 큰 크기로 새로운 배열을 생성하고, 기존 배열에 있었던 데이터를 전부 복사하는 작업을 진행하는데 이를 더블링 이라 한다. 더블링 소요시간은 기존 가지고 있던 데이터 길이가 n 이라 할 때 O(n) 만큼이 소요된다. 

 

 

 

ArrayList 성능 

---

검색시간은 고정된 배열에서 검색되기 때문에 O(1) 이다. 

입력시간 또한 더블링 이슈가 있음에도 O(1) 으로 표현할 수 있다. 

더블링 시, 기존 배열의 크기는 새로운 배열 크기의 절반이다. 즉, 새로운 배열에 복사해야되는 양은 현재 배열방의 크기의 절반인 셈이다. 

 

2/n      +     4/n     +      8/n    +     16/n    ...    2       +       1 
      직전       그 전 직전        그 전 직전의 직전       2개일 때      1개일 때

 

이를 다 더해도 합이 n 보다 작다. 합이 n에 다가가더라도 2배씩 커지기 때문에 복사하는 총 데이터가 n 보다 커지지 않는다. 

하지만, 최악의 경우 값을 추가할 때 더블링 이슈가 발생하면 n개만큼 복사하는 시간을 기다려야 해서 이 경우에는 입력 시간복잡도가 O(n) 으로 표현할 수 있다. 

 

 

 

LinkedList 란?

---

ㄴ 길이가 정해져있지 않은 데이터의 연결된 집합

ㄴ 단방향/양방향 연결리스트가 있다.
 

단방향 연결리스트

 - header 주소 하나만 가지고 있고, 한쪽으로만 이동이 가능하다. 

 - 각각의 노드는 다음 노드의 주소를 가지고 있다.

 - 자바의 경우 tail 주소도 저장하고 있어, 시작과 끝 노드의 삽입 삭제시 O(1) 의 시간복잡도를 가질 수 있는 것이다.

 

양방향 연결리스트 

 - header, tail 주소를 저장하고 있어, 맨 끝에 노드를 삽입할 때 끝까지 찾아가는 번거로움을 줄일 수 있다. 

 - 각 노드는 이전 노드의 주소와 다음 노드의 주소를 가지고 있어 양 방향으로 움직 일 수 있다는 특징을 가지고 있다.

 

LinkedList 구현

https://hyokeun0419.tistory.com/48

 

 

 

LinkedList 특징

---

ㄴ 특정 인덱스를 상수시간에 접근할 수 없다.

    (특정 K 번째 원소를 찾고싶으면, K 번 루프를 돌아야한다.)

ㄴ 시작과 끝 지점에서 추가, 삭제 연산을 상수시간에 할 수 있다.

 

 

 

Array vs ArrayList vs LinkedList 

---

Array & ArrayList

 

Array & ArrayList & LinkedList 시간복잡도

 

 

 

5. Script 

---

데이터를 추가하는데로 사이즈가 늘어나는 자료구조이다.

ArrayList는 내부적으로 데이터가 가득 차면 현재 배열보다 2배 큰 크기로 새로운 배열을 생성하고 기존배열에 있던 데이터를 전부 복사하는 작업을 진행하는데 이를 더블링이라 한다. 

데이터 입력시 더블링이 발생하면, 소요시간은 기존 가지고 있던 데이터 길이가 n 이라 할 때 O(n) 만큼이 소요되는데, 평균적으로는 데이터 입력은 O(1) 으로 표현 할 수 있다. 기존 배열의 크기는 새로운 배열 크기의 절반인데, 복사되는 총 데이터가 새로운 배열보다 클 수 없기 때문이다. 그럼에도 최악의 경우에는 더블링이 발생되는 순간에는 O(n) 의 시간복잡도를 가질 수 있다.

 

LinkedList는 배열 길이가 정해져있지 않은 데이터의 연결된 집합이다. 

배열과 달리 특정 인덱스를 찾고 싶으면 처음부터 순회를 해야하며, 시작과 끝 지점에 추가&삭제 연산을 상수시간에 할 수 있다는 특징이 있다.