[Java] Java LinkedList

배열의 장단점

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

단점 :
1. 크기를 변경할 수 없다.
- 크기를 변경해야하는 경우 새로운 배열을 생성 후 데이터를 복사해야 함
- 크기 변경을 피하기위해 처음부터 큰 배열을 생성하면 메모리가 낭비됨

2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
- 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 함
- 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.
(배열 중간의 있는 데이터를 추가하거나 삭제하는걸 말하고, 중간이 비어버리면 뒤에있던 데이터의 자리를 이동하는데 시간이 많이 걸림)

 

배열의 크기를 변경하는 법
① 더 큰 배열 생성 ② 데이터 복사 ③ 참조를 변경

 

 

배열의 단점을 보완하려고 나온게 LinkedList 이다.

 

 

 

LinkedList

LinkedList는 불연속적으로 존재하는 데이터를 하나하나 연결한다. (aka. 기차)

배열은 각 요소가 연속적으로 다닥다닥 붙어있어 다음 요소 주소를 정확하게 알 수 있다. (aka. 박스)

 

 

• 연결 리스트
• 각 데이터가 어디있는지 알 수 없고, 하나의 개별 요소를 연결해둔 것이다. 
• 요소 하나당 노드라고 부름

 

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

• 중간 요소를 삭제하고싶을때는 단순히 연결만 바꾸면 된다.

 

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

 

LinkedList 장단점

장점 :
변경에 유리함

단점 :
데이터 접근성이 나쁘다. (불연속적이라 오른쪽인 다음 요소는 알아도 한번에 여러개 이동은 불가)
징검다리를 연상해보자. 한번에 이동은 불가하고 한발 한발 이동해야함

 

 

 

doubly linked list 

• 이중 연결 리스트
• 접근성 향상 (LinkedList의 접근성이 나쁜걸 개선함)
• 서로 근접한 두 요소를 앞뒤로 이동할 수 있게 연결해둔 것
• 참조를 2개 갖고있다 (이전, 다음 요소)
• 새로운 요소를 추가/삭제시 참조를 2번 변경해야하므로 시간이 더 걸림 

 

앞뒤로 이동만 좋아졌을뿐, 한번에  두세개 요소를 건너뛰는건 불가하므로 

여전히 배열에 비해서는 접근성이 나쁘다. 👎👎

 

 

 

doubly circular linked list

• 이중 원형 연결리스트
• 이중연결리스트를 더 개선한 것
• 이중연결리스트 마지막 양끝의 요소가 null인 값을 활용함
• 마지막 요소의 다음을 맨 앞 요소와 연결, 맨 앞 요소를 맨 끝 요소와 연결

 

TV 채널 이동을 연상해보자. ch1에서 아래로 이동하면 ch999로 이동하는것과 같은 원리다.

 

 

 

 

ArrayList vs LinkedList 

 

성능비교

 

- 순차적으로 데이터 추가/삭제 

→ ArrayList가 빠름

 

- 비순차적으로 데이터 추가/삭제 (중간에 추가하기)

→ LinkedList가 빠름

 

- 접근시간테스트

→ ArrayList가 빠름

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

 

 

 

정리

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

 

 

 

Ref

http://changpd.blogspot.com/2014/08/arraylist-linkedlist-java.html