03. [자바] LinkedList의 자료구조

다른 컬렉션, 자료구조에 대해 궁금하다면 아래의 링크를 클릭해보자👍

01. [자바] 컬렉션 프레임워크(Collections Framework)

---

LinkedList의 자료구조?

배열은 가장 기본적인 자료구조이다, 구조가 간단하고 사용하기 쉽고 데이터를 읽는 시간이 가장 빠르다는
장점을 가지고 있지만 단점 또한 있다.

1. 크기를 변경할 수 없다.
 * 배열의 크기를 변경하려면 번거롭게 원하는 크기의 배열을 생성하고 
   기존 배열의 데이터를 복사해야한다.

 * 실행속도를 향상시키기 위해서는 위와 같은 과정이 생기지 않게 
   충분히 큰 크기의 배열을 생성해야 하는데 이로 인해 메모리가 낭비된다.

2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
 * 차례대로 데이터를 추가하거나 마지막에서부터 데이터를 삭제하는 것은 빠르지만
 * 배열의 중간에 데이터를 추가하려면 빈자리를 만들기 위해 
   다른 데이터들을 복사해서 이동해야한다.

LinkedList는 위와 같은 배열의 자료구조를 보안하기 위해 만들어졌다.
배열은 모든 데이터가 연속적으로 존재하지만

링크드 리스트는 연속적이지 않은 데이터를 서로 연결(link)한 형태로 구성되어 있다.

node간 주소값을 이용한 연결

그림에서 확인 가능 하듯이 링크드 리스트의 각 요소(node)는 자신과 연결된 다음 요소에 대한 주소값과

데이터로 구성되어 있다.

 

 

데이터의 삭제는 삭제하고자 하는 노드의 이전 노드가 삭제하고자 하는 노드의 다음 노드를 참조하도록

변경하면 되기 때문에 속도가 빠르다.

LinkedList의 노드 삭제

 

 

데이터의 추가도 노드를 생성 후 추가하고자 하는 위치의 이전 노드의 참조를 추가되는 노드를 참조하게 하고

추가된 노드가 그 다음 노드를 참조하게 변경하면 되기 때문에 속도가 빠르다.

LinkedList의 데이터 추가

 

 

 

링크드 리스트는 이동방향이 단방향이기 때문에 이전 노드에 대한 접근이 어렵다.

이 점을 보완하여 만들어진 것이 더블 링크드 리스트(이중 연결리스트, doubly linked list)이다.

참조변수를 하나 추가하여 이전 노드를 참조 가능하게 만들었다.

이중 연결리스트, doubly linked list

실제 LinkedList클래스는 이름과 달리 더블 링크드 리스트로 구현되어 있고 그 이유는 낮은 접근성을
높이기 위해서 이다. 여기까지가 LinedList의 기본 원리이다.

 

 

 

 

추가로 더블 링크드 리스트보다 더 접근성이 좋은 것이 더블 써큘러 링크드 리스트 이다.
뭔가 어릴적에 이름이 슈파 파워 울트라 깹숑 처럼 길어지면 강해진다고 느끼던 감성이랑 비슷한 건지..
처럼 이름이 점점 길어진다, 무려 더블 써큘러 링크드 리스트이다.😑
이 엄청난 더블 써큘러 링크드 리스트는 더블 링크드 리스트의
첫 노드와 마지막 노드를 서로 연결시킨 것이다.
이렇게 하면 마지막 노드의 다음 노드가 첫 번째 노드가 되고 첫 번째의 이전 노드가 마지막 노드가 된다.

이중 원형 연결리스트, doubly circular linked list