[Java] 컬렉션 프레임워크3_List_LinkedList

이 게시글은 남궁성의 정석코딩 - 자바의 정석 기초편(2020최신)을 보고 공부한 내용을 정리한 게시글입니다.
틀린 내용이 있을 수 있습니다.

 

 

 

✔ LinkedList

배열의 단점을 보완하는 클래스이다.

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

배열의 단점2. 비순차적 데이터의 추가, 삭제에 시간이 많이 걸린다.
- 데이터를 추가하거나 삭제하기 위해 다른 데이터를 옮겨야 한다.
- 하지만 순차적에 데이터 추가(끝에 추가), 삭제(끝에 삭제)는 빠르다.

 

LinkedList는 불연속적으로 존재하는 데이터를 연결한다.

아래 그림으로 배열과 LinkedList의 차이를 확인할 수 있다.

 

[배열]

배열은 연속적이다. ex) 상자

중간에 데이터를 추가, 삭제 하게 되면 다른 데이터들이 이동해야 해서 시간이 많이 걸린다.

 

 

[LinkedList]

LinkedList는 각각 존재하는 데이터(노드)를 연결한다. ex) 기차

중간에 데이터를 추가, 삭제하게 되면 화살표의 방향만 바꾸면되서 시간이 짧다.

 

 

 

 

◾ linked list의 발전

 

linked list

LinkedList는 데이터 접근성이 나쁘다.

하나의 데이터는 다음 데이터만 가리키므로,

맨 뒤에 있는 데이터에 접근하려면 앞에 있는 데이터를 모두 거쳐야 한다.

또한 앞에 있는 데이터로 갈 수 없다.

 

 

doubly linked list

이러한 단점을 개선시킨 것이 더블리 링크드 리스트(doubly linked list)이다.

이중 연결리스트로 하나의 데이터에서 앞, 뒤 데이터로 접근할 수 있다.

 

 

doubly circular linked list

더블리 링크드 리스트에서 한 단계 더 개선한 게, 더블리 써큘러 링크드 리스트(doubly circular linked list)이다.

이중 원형 연결리스트로 처음에서 끝으로 바로 갈 수 있고, 끝에서 처음으로 바로 갈 수 있다.

 

하지만 여전히 첫 번째 요소에서 세 번째 요소로 건너뛰기 할 수는 없다.

 

 

 

 

◾ ArrayList와 LinkedList의 성능 비교

순차적으로 데이터 추가 소요시간	ArrayList	<	LinkedList
순차적으로 데이터 삭제 소요시간	ArrayList	<	LinkedList
중간에 데이터 추가 소요시간	ArrayList	>>	LinkedList
중간 데이터 삭제 소요시간	ArrayList	>>	LinkedList
데이터에 접근하는 시간 소요시간	ArrayList	<<	LinkedList

 

★결론★

순차적인 데이터 추가, 삭제는 ArrayList가 빠르다.

비순차적인 데이터 추가, 삭제는 LinkedList가 빠르다.