[자바의 정석 기초편 chapter 11] LinkedList

배열은 장점과 단점이 있다!

 

🟨 장점

구조가 간단, 사용이 쉬움, 데이터를 읽어오는 데 걸리는 시간이 가장 빠름

 

🟥 단점

1. 크기를 변경할 수 없다.

- 크기를 초과할 시 새로운 배열을 생성해서 데이터를 복사해야됨

- 실행속도 향상을 위해서 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비됨

 

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다. 

- 배열 중간에 데이터를 추가할 시, 다른 데이터들을 복사해서 이동시켜야 함

 

이런 배열의 단점을 보완하기 위해서  고안된 자료구조가 링크드 리스트(linked list)이다!

 

 

 

🟦 링크드 리스트(linked list)란?

불연속적으로 존재하는 데이터를 서로 연결(link) 한 형태로 구성되어 있다. 

링크드 리스트의 각 요소를 노드(node)라고 하고, 노드는 데이터와 자신과 연결된 주소값으로 구성되어 있다. 

위 그림에서 D1이 데이터/ 화살표가 있는 네모가 주소값이 저장되는 곳이라고 보면 된다. 

주소값이 저장되는 곳을 아래에 코드에서 next로 표현!

class Node{
	Node next; //다음요소의 주소를 저장
    	Object obj; // 데이터를 저장
}

 

직접 그려봤다!

ㅋㅋㅋ

 

 

 

🟦 링크드 리스트(linked list)의 추가와 삭제

 

링크드 리스트의 삭제는 간단하다. 

삭제하기 전 후의 요소들이 서로 참조하도록 변경해주면 됨!

배열처럼 데이터를 이동하기 위해 복사는 과정이 없이 단 하나의 참조만 변경하면 되므로  처리속도가 매우 빨라짐

링크드 리스트의 추가도 간단하다. 

추가하고자 하는 위치에 요소를 추가한 후 추가한 데이터의 전 후 요소들의 참조를 변경해주면 된다. 

근데 링크드 리스트의 단점도 있다. 

데이터의 접근성이 나쁘다! 첫 데이터에서 맨 끝 데이터로 이동하려면 순차적으로 데이터들을 건너가야 함

 

그래서 접근성이 향상된 더블리 링크드 리스트가 있다(doubly LinkedList)

 

🟩더블리 링크드 리스트(dubly LinkedList)

링크드 리스트가 단방향이라면 더블리 링크드 리스트는 양방향! 이중연결이다. 

다만 첫 데이터와 끝 데이터는 전 데이터와 연결이 안 되어 있음

 

그래서 접근성을 더 향상한 더블리 써큘러 링크드 리스트(doubly circular LinkedList)가 있다.

class Node{
	Node next; //다음 요소의 주소를 저장
    	Node previous; //이전 요소의 주소를 저장 
    	Node obj; //데이터
}

 

🟧 더블리 써큘러 링크드 리스트(doubly circular LinkedList)

이중원형 연결 리스트라고 불리며 더블리 링크드 리스트가 처음과 끝 연결이 안 되어 있던 단점을 보완함!

더블리 써큘러 링크드 리스트는 처음과 끝을 서로 연결시켜놔서 처음 데이터 이전은 맨 끝으로. 맨 끝 데이터 다음은 맨 처음으로 이동시켜 준다.

 

다만 이 친구도 중간 데이터로 한 번에 건너뛰기는 안 됨 ^^;

 

 

그럼 ArrayList와 LinkedList를 비교해 보자!

ArrayList는 주소값 계산이 쉬워서 저장된 데이터를 곧바로 얻어올 수 있지만 

LinkedList는 불연속적으로 위치한 요소들이 서로 연결된 것이라 처음부터 n번째 데이터까지 차례대로 따라가야 해서 데이터의 개수가 많아질수록 데이터를 읽어오는 접근시간이 길어진다!ㅠ

 

 ArrayList에서 인덱스가 n인 데이터의 주소

= 배열의 주소 + (n × 데이터 타입의 주소)

 

즉, 순차적인 데이터 추가/삭제는 ArrayList가 빠르고

비순차적인 데이터 추가/삭제(중간에 있는 데이터 추가/삭제를 말함)는 LinkedList가 빠르다

 

접근시간은 ArrayList가 빠르다.