LinkedList

배열의 장단점

이번시간에는 LinkedList에 대해서 알아 볼 것인데,
그전에 먼저, 배열의 장단점에 대해서 알아보자.

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

배열은 구조가 간단하고, 데이터를 읽는데 걸리는 시간이 짧다.
첫번째 데이터에 접근하는데 걸리는 시간과 마지막 데이터에 접근하는데 걸리는 시간이 같다.

배열은 연속적이다.
int배열이라고 봤을 때, 배열의 인덱스 1개당 4byte의 공간을 가지고 있다.
만약에 시작이 100번지면,그다음은 104번지, 108번지 이런식으로 된다.
그러면, 해당 배열의 n번째의 요소를 읽으려면,
배열의 시작주소를 s라고 했을 때, s + (4 * n) 해주면 접근할 수 있을 것이다.
이런식으로  [배열의 주소+ ( 배열요소의 크기 * 인덱스)]  를 해주면,
인덱스 + 1번째요소의 주소에 접근할 수 있다.

예를 들어, 위의 그림에서 3번째 요소인 3에 접근하려면, 0x100 + 4 * 2를 해주면 된다.

 

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

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

배열에 새로운 데이터(6)를 추가하고싶은데, 넣을 공간이 없으면,
1. 더 큰 배열을 생성
2. 기존 배열의 요소를 복사
3. 참조 변경
4. 새로운 데이터(6) 추가
이러한 과정을 거쳐야 한다.

크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비됨.
그래서 ArrayList(int initial) 을 이용해서 배열을 생성할 때 적절한 길이를 생성해야 한다.
내가 저장하려는 객체의 갯수를 예상해서 그것보다 좀더 넉넉하게 지정해주는 것이 좋다.

 

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

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

배열의 또다른 단점으로는, 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다는 것있다.

중간에 있는 데이터를 삭제하게 되면, 해당 데이터의 뒤에있는 요소들이 자리를 옮겨야 하기 때문이다.
만약에, 삭제할 데이터의 뒤에 엄청난 양의 데이터가 있으면 훨씬 오래 걸릴 것이다.

물론, 배열의 이러한 단점을 보완하기위해 데이터를 이동시키지 않는 방법도 있지만,
이번시간에는 ArrayList가 빈자리를 채우도록 다른 요소들을 옮기게 되어있기때문에 이러한 단점이 있다는 것이다.

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

무조건 느린건 아니고,순차적인 데이터추가 즉, 맨 끝에 추가/삭제 하는 것은, 빠르다.

 

---

 

LinkedList - 배열의 단점을 보완

 

방금전 배열의 장단점에 대해서 알아봤는데,
배열의 단점은
1. 크기 변경불가
2. 추가/삭제 시간이 많이 걸림

이러한 단점을 보완하기 위해서 나온것이 LinkedList이다.

 

• 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결(link)

 

배열은 각 요소가 위의 그림처럼 연속적인 반면,

 

- LinkedList는 그림은 나란히 그려놓았지만, 각요소가 연속적이지 않다. (불연속적)

LinkedList는 요소하나하나를 연결 해놓은 것이다.
그리고 요소 하나를 Node라고 한다.

Node클래스를 보면, Node로 다음에 지정할 요소의 주소를 저장할 수 있고,
Ojbect에는 현재 노드에 저장된 데이터가 있다.

- 데이터의 삭제 : 단 한번의 참조변경만으로 가능
중간에 요소를 삭제하려면, 단순히 삭제할 데이터의 이전 노드를 삭제할 데이터의 다음노드에 연결시키면 된다.

 

 

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

데이터를 추가하려면, 새로운 것을 만들고, 추가할 위치의 이전 인덱스의 노드가 새로운 데이터의 주소를 가리키도록 하고,
새로운 데이터의 노드는 위치할 곳의 다음 인덱스에 있는 데이터의 주소를 가리키도록 하면 된다.

즉, 참조변경만 두번 하면 데이터를 추가할 수 있다.

 

 

하지만, LinkedList에도 분명 단점은 존재한다.

- 링크드 리스트 (Linked list) LinkedList는 데이터 접근성이 나쁘다.

배열은 각요소가 연속적이어서 아무리 데이터가 많아도 한번에 찾아갈 수 있는데,
LinkedList는 불연속적이어서 바로 다음요소는 한번에 찾을 수 있지만, 그이상은 한번에 찾을 수 없다.
자기다음밖에 모르기 때문이다.

이것을

그래서  LinkedList의 접근성이 나쁜 것을 개선한 것이 바로 "이중 연결 리스트"이다.

 

 

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

doubly linkde list는 서로 근접한 두 요소를 앞뒤로 이동할 수 있도록 연결해 놓은 것이다.
그래서 Linked List는 참조가 next밖에 없는데,
doubly linked list는 참조를 next와 previous 2개를 가지고 있다.

이전요소를 가지고 있기 때문에 앞뒤로 이동이 가능하다.

대신에, 새로운 요소를 추가하거나 삭제할 때는, 두 개의 연결을 맺어주고 끊어주고 해야하기 때문에 시간이 더 걸린다.
그러나, 앞뒤로 이동이 가능하다는 점떄문에, linked list에 비해서 접근성이 더 좋아졌다.

그러나, 여전히 한번에 두개세개씩 건너뛰는 것은 안된다. 앞뒤로의 이동만 좋아졌을 뿐이다.

 

 

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

그다음, 이 이 중 연결 리스트를 개선한 것이 "이중 원형 연결 리스트"이다.
앞서 doubly linked list의 그림을 보면, 양끝에 있는 노드중 첫번째노드의 이전 노드와, 마지막 노드의 다음노드는 null인 것을 확인할 수 있는데,

이 값을 활용해서 마지막 요소의 다음을 맨 앞의 요소와 연결하고,
맨 첫번째요소를 맨 끝의 요소와 연결해 놓는 것은 것이다. (그래서 원형임)

그래서, 맨 처음에서 끝으로 갈 때, 링크드 리스트에서는 위의 그림 기준으로 4번 이동해야하지만,
이중 원형 연결 리스트에서는 바로 이전 요소로 가면 맨 끝으로 갈 수 있다. 
TV에서 채널1일때 채널0이되는 것이아니라, 제일 마지막 채널로 가는 것과 같은 원리라고 보면 된다.

 

---

 

ArrayList vs Linked List - 성능 비교

 

이번에는 ArrayList와 LinkedList의 성능을 비교해보자.

자바의 정석3판에 있는 예제인데, 결과만 살펴보도록 하자.
단위는 ms이다.

1. 순차적으로 추가/삭제하는 것은 ArrayList가 빠르다.
2. 비순차적으로(중간에) 데이터를 추가삭제 하는 것은 Linked List가 빠르다.
3. 접근시간(access time) - ArrayList가 빠르다.

배열은 n번째 요소에 접근하려면 위의 공식만 계산하면 된다.

그런데, 링크드 리스트는 데이터가 많을 수록 하나하나 방문해야 하므로 시간이 훨씬 많이 걸린다.

 

정리해보면,

읽기는 ArrayList가 빠르고,
순차적인 변경에는 ArrayList 빠르지만
비순차적인 변경에는 LinkedList가 빠르다.

ArrayList가 비효율적인 메모리사용이 있을수 있다는 건,
성능을 높히기 위해서 배열을 크게 잡아야 하기 때문이다.
배열이 단점이 데이터 복사나 이동이 문제인데,
그것을 적게 일어나도록 하려면 배열을 크게잡아야 하기때문에 아무래도 메모리를 비효율적으로 사용할 확률이 크다.

그에반에 Linked List는 필요할 때마다 하나씩 만들어 사용하므로 메모리 낭비가 없다.
대신에 Linked List의 단점은 데이터가 많을수록 접근성이 떨어진다는 것이다.

 

자료구조에서는,
ArrayList는 배열기반의 자료구조,
Linked List는 연결기반의 자료구조라고 한다.

배열기반과 연결기반의 장단점을 비교한 내용을 잘 기억해두자.