LinkedList 와 ArrayList 의 비교

ch11- 12 LinkedList - 배열의 장단점

 

장점 : 

 

배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간이 짧다.

(접근 시간, access time 이 짧다)

 

 

첫번째 요소를 읽는것과 마지막 요소를 읽는 시간이 동일 하다.

 

만약, int 타입의 배열 [ ] 이라고 가정 하면,

 

요소 하나당 4byte를 차지하므로, 

 

1은 0x100

2는 0x104

3은 0x108

4는 0x112

5는 0x116

 

일것이다.

 

3번째 요소를 가지고 오려면,

 

0x100 번지 주소에서 배열 요소의 크기 (int 타입 이니까 4byte) 에 index 를 곱하면 

n번째 요소의 주소를 쉽게 구할 수 있다.

 

만약에 n번째 요소가 100번째 라고 했어도,

 

0x100 번지 + (4byte * 100) 을 하면 바로 해당 요소의 주소값을 구할 수 있게 된다.

 

단점 1 :

 

배열은 크기를 변경할 수 없다.

 

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

 

(이미 실행이 된 경우에 크기를 변경 할 수 없다는 의미 이다)

 

 

위와 같이 길이가 더 큰 배열을 생성 하고, 기존의 배열을 복사하고,

기존 배열을 가리키는 참조변수는 새롭게 만든 더 큰 배열을 가리킬 수 있게 변경해 줘야 한다.

 

이게 불편하다고 해서 처음 부터 배열을 크게 만들어 놓으면, 그건 또 메모리 낭비가 되게 된다.

 

그래서, 배열을 생성 할 때는 길이를 잘 정해주는것이 중요 하다.

그래야만, 배열을 새롭게 생성하는 수고로움이 줄어들기 때문 이다.

보통, 배열의 공간이 부족하면, 기존 배열의 2배의 길이의 새로운 배열을 생성하곤 한다.

(반드시 그러는것은 아니고 ..)

 

단점 2 :

 

비순차적인 데이터의 추가 및 삭제에 시간이 너무 많이 걸린다.

 

배열의 요소에서 중간에 있는 요소를 삭제 하거나, 추가 하면 자리를 이동 해야 하기 때문에 이다.

 

하지만, 무조건적으로 데이터 추가 및 삭제가 오래 걸리는게 아니라,

 

맨 마지막 번째의 index에 요소를 추가 하거나 또는 삭제 하면 그것은 자리 이동이 필요 없으므로 빠르다.

 

 

 

ch11 - 13 LinkedList - 배열의 단점을 보완

 

기존 배열 [ ] 은 한번 컴파일 되면 크기 변경이 불가능 하다.

 

물론, ArrayList 는 한번 컴파일이 되더라도, 가변적으로 배열의 크기가 변경 될 수 있으나,

(ArrayList를 생성 할 때 길이를 지정해 주지 않으면 디폴트 길이는 10 으로 알고 있다)

(만약 디폴트 길이를 초과하는 경우, 알아서 길이를 확장한다)

 

어찌 됬던 배열 이든 ArrayList 이든 추가와 삭제의 시간이 많이 소요 된다는 단점을 가지고 있다.

 

- 배열과 달리 링크드 리스트는 불연속적으로 존재하는 데이터를 연결 한다.

== link

 

(배열과 배열리스트는 연속적으로 존재 하기 때문에 변경과 삭제가 어려운 것이다)

 

- 데이터의 삭제 : 단 한번의 참조를 변경 하는 것으로 가능 하다.

 

 

각 요소들은 모두 주소값이 중구난방 이다.

 

주소값이 중구난방인 각 요소들을 (데이터를) 연결해놓은 것이다.

 

즉, 데이터 하나 하나를 연결해 놓았다고 보면 된다.

 

이러한 데이터 요소 하나를 " 노드 " 라고 한다.

 

그래서 변경에 매우 유리한 장점을 가지고 있다.

 

만약에 중간에 요소를 삭제 하고 싶으면, 그냥 삭제 하면 된다.

 

참조 변수가 가리키는 주소값을 그냥 변경 해주고 연결을 변경해 주면 된다.

 

- 데이터의 추가 : 한번의 Node 객체 생성과 두 번의 참조를 변경 하는것으로 가능 하다.

 

 

 

 

링크드 리스트 (LinkedList) 의 단점 : 데이터 접근성이 나쁘다.

 

 

이게 무슨말이냐면,

전체의 요소가 연속적인 구조가 아니기 때문에,

자기 다음만 알고 있다는 의미 이다.

첫번째 요소는 두번째 요소만 알지, 세번째 요소를 모르기 때문에,

첫번째 에서 세번째로 바로 갈 수가 없다.

즉, 한번에 바로 갈 수가 없다. == 데이터의 접근성이 나쁘다.

 

뿐만 아니라, 오른쪽으로만 갈 수 있다. 자기 다음 요소만 알지, 이전 요소는 알지도 못한다.

(연속적인 구조가 아니니까)

 

그래서 이것을 보완 하기 위해서 아래와 같은 개념이 있다.

 

더블리 링크드 리스트 == Doubly Linked List - 이중 연결리스트, 접근성 향상

 

 

그래서 더블리 링크드 리스트의 노드 객체 하나에는,

이전 요소와 그 다음 요소를 모두 알 수 있도록 참조를 두개를 가지고 있다.

 

 

대신에 새로운 요소를 중간에 추가 하게 되면,

기존에 링크드 리스트는 참조를 한개만 연결해 주면 됬었는데,

두개의 참조를 연결해 줘야 한다는 번거로움과 시간의 부담 요소가 생겼다.

 

하지만 여전히 두개, 세개의 요소를 건너뛰는건 여전히 불가능 하다.

 

단지 앞, 뒤의 접근성이 가능해진것 뿐이다.

 

그래서, 위의 더블리 링크드 리스트를 더욱 개선한 것이 아래에 있는 더블리 서큘러 링크드 리스트 이다.

 

더블리 서큘러 링크드 리스트 == Doubly Circular Linked List - 이중 원형 연결리스트

 

 

그런데, 실제로 자바 표준 라이브러리 에서는 더블리 서큘러 링크드 리스트 클래스를 제공 하지는 않는다.

 

 

 

ch11 - 14 ArrayList vs LinkedList - 성능 비교

 

1) 순차적으로 데이터를 추가 / 삭제 - ArrayList 가 더 빠르다.

 

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

(중간에 추가 / 삭제 하는것을 의미 한다)

 

3) 접근 시간 (access time) - ArrayList 가 더 빠르다.

(인덱스가 n 인 데이터의 주소 = 배열의 주소 + ( n * 데이터 타입의 크기 )

 

 

성능 테스트 결과 예시 (밀리 세컨드)

 

숫자가 클수록 시간이 더 오래 걸렸다는 의미.

 

컬렉션	읽기 (접근 시간)	추가 / 삭제	비고
ArrayList	빠르다	느리다	순차적인 추가 삭제는 더 빠름 비효율적인 메모리 사용
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어짐

 

[ 정리 ]

 

자료 구조 에서

 

ArrayList 는 배열 기반 이라고 부르고,

LinkedList 는 연결 기반 이라고 부른다.

 

모든 자료 구조는 배열 기반 또는 연결 기반 으로 만들어져 있다.

 

배열 기반의 특징은 연속적이고,

 

연결 기반의 특징은 불연속적이다.