collection framework : LinkedList

배열의 장단점 

장점: 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근시간, access time)이 짧다.

배열은 연속적이라서 첫번째 요소를 읽는 시간이랑 마지막 요소를 읽는 시간이랑 같다.

 

내가 배열의 요소를 찾고자 하면 == 해당 배열의 주소 + (배열의 요소의 타입 크기 X index)

예를 들어 내가 찾고하는 배열이 int[ ] arr 배열이고 해당 주소가 0x100이다. 

이때 내가 찾고자 하는 배열의 요소가 arr [10]이면, 0x100에서 배열의 타입이 int이기에 4byte와 index 10을 곱하면된다.

그래서 배열의 주소 == 0x100 + 4X10 즉, 0x140이 된다. 

이렇게 배열의 요소만 알고 있어도, 쉽게 계산이 가능하기에 

배열의 요소를 찾는 속도는 매우 빠르다.

 

단점1: 크기를 변경할 수 없다.

크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야한다.

그래서 만약 내가 값을 추가하려고 할때 배열의 크기가 꽉 찬 상태라면, 

1. 더 큰 새로운 배열을 생성한다.

2. 기존의 배열을 새로 생성한 배열에 복사한다.

3. 참조변경한다.

크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리 낭비가 된다.

 

단점2: 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.

1. 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 함.

왜냐하면 중간에 데이터를 추가 및 삭제를 하게 되면 그 기준으로 변경된 시점으로부터 변동이 있는 데이터 전부 이동하기 때문이다.

예를 들어, a[0] ~ a[10]까지의 배열이 존재했을때 a[3]을 삭제하면 a[4]~a[10] 배열의 요소가 한칸씩 왼쪽으로 다 옮겨진다.

그래서 배열은 시간이 많이 걸린다.

2. 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다. 

---

LinkedList

이러한 배열의 단점(크기 변경 X, 데이터 추가/삭제 시간 높음)을 보완하기 위해 나온게 LinkedList이다.

배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)

데이터의 삭제 : 단 한 번의 참조 변경만으로 가능

class Node {
    Node Next;
    Object obj;
}

데이터의 삭제 : 단 한번의 참조변경만으로 가능

삭제하고자 하는 노드 이전과 다음 노드의 주소값에서 삭제한 노드 주소값이 아닌 

이전/다음 노드의 주소값으로 바꿔준다.

그러면 삭제할 노드는 GC(Garbage Collector)에 의해 삭제된다.

 

 

데이터 추가: 한번의 Node객체생성과 두 번의 참조변경만으로 가능

LinkedList는 Node 객체를 가지고 있다. Node 객체는  기차처럼 한칸씩 연결되어 있다.

이때, 내가 만약 데이터를 추가하고 싶으면 원하는 위치에 노드에서 이전 노드와 이후 노드에서 작업이 필요하다.

이전 노드는 다음 노드 주소를 새로운 노드로

다음 노드의 이전 노드 주소를 새로운 노드로

바꿔주면 데이터 추가가 되며 기존의 변경 전 노드는 GC(Garbage Collector)에 의해 사라진다.

그리고 배열과 달리 바뀐 데이터 이후 값들을 전체 이동할 필요가 없다.

그래서 데이터 추가 삭제가 빠르나, 배열에 비해 데이터 조회는 느리다.

왜냐하면 LinkedList의 노드들을 바로 앞뒤의 데이터 주소만 알지 전체의 주소를 파악할 수 없기 때문이다. 

 

링크드 리스트(linked list) - 연결리스트 / 데이터 접근성이 나쁨

불연속적이다. 그래서 자신의 데이터 다음 데이터로 이동은 가능하나 건너뛰고 다음(예: 두칸 앞으로)으로 가는 것은 불가능하다(배열처럼 한번의 이동 불가)

배열은 몇번째 인덱스인지를 파악하여 이를 연사하여 바로 이동 가능함.

그러나 링크드 리스트는 해당 배열로 가기 위해서는 한칸씩 이동해서 가야함.

 

 

더블리 링크드 리스트(doubly linked list) - 이중 연결리스트, 접근성 향상

링크드 리스트의 단점을 보완하고자 앞 뒤로 이동할 수 있게 함.

하나의 노드가 이전 노드의 주소와 다음 노드의 주소를 가지고 있기에 앞뒤 이동은 가능하나

배열처럼 한번에 건너뛰어 이동은 안되고 한 칸씩 이동해야한다.

class Node{
   Node next;
   Node previous;
   Object obj;
}

 

더블리 써큘러 링크드 리스트(doubly circular linked list) - 이중 원형 연결리스

마지막 요소의 다음 노드 주소를을 맨 처음 요소와 연결

맨처음 요소의 이전 노드 주소를 맨 마지막 요소와 연결

Tv에 체널 1번에서 버튼을 아래로 내리면 마지막 체널 99로 바뀌는 것과 동일

 

 

ArrayList vs LinkedList - 성능 비교

1. 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름

2. 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름

3. 접근시간(access time) - ArrayList가 빠름

ArrayList : 배열기반 자료구조

LinkedList: 연결기반 자료구조