자료구조 - [ 이중 연결 리스트 ]

1. 이중 연결 리스트

 

이중 연결 리스트의 노드는 데이터와 좌측 노드의 참조값을 저장하는 변수, 우측 노드의 참조값을 저장하는 변수가 있다.

 

 

 

 

구성은 크게 head, tail 그리고 노드가 있다.

• head : 첫 번째 노드를 가리키는 노드 또는 변수
• tail : 마지막 노드를 가리키는 노드 또는 변수
• 노드 : 데이터, 좌/우측 노드로 접근할 수 있는 참조값을 가지고 있음

 

 

 

---

1) 장점

- 데이터의 크기가 예측 불가능할 때 사용할 수 있다.

- 필요한 만큼만 메모리 공간을 사용 -> 배열보다 상대적으로 메모리 절약 가능

- 단일 연결 리스트와 다르게 양방향 연결을 지향하므로 뒤 쪽에 있는 노드 접근 시 tail을 이용하면 더 빠르게 접근 가능

   ex) 노드의 개수가 10000개일때 9821번째 노드에 접근하려면 tail을 이용할 때 훨씬 빠름

 

2) 단점

- 단일 연결 리스트보다 구현이 복잡

- 노드의 참조값을 저장하는 변수가 하나 더 추가되므로 단일 연결 리스트보다 메모리 공간을 더 많이 사용

 

 

---

2. 이중 연결 리스트 삽입

1) 최초로 노드 삽입

새로운 노드 생성 후 head와 Tail에 새로운 노드의 참조값 저장

 

---

2) 맨 앞에 노드 삽입

1. 새로운 노드 생성 후

2. head가 가리키는 노드의 참조값을 새로운 노드의 right 변수에 저장

3.새로운 노드의 참조값을 head가 가리키는 노드의 left 변수에 저장

4. head는 새로운 노드의 참조값 저장

 

 

 

---

3) 맨 뒤에 노드를 삽입

1. 새로운 노드 생성

2. tail이 가리키는 노드의 참조값을 새로운 노드의  left 변수에 저장

3. 새로운 노드의 참조값을 tail이 가리키는 노드의 right 변수에 저장

4. tail에 새로운 노드의 참조값 저장

 

 

 

---

4) 중간에 노드 삽입

0. pointer 기준 좌측 노드의 참조값을 저장

=> 좌/우측 노드의 참조값을 임시 변수에 저장하면 연결 순서는 크게 상관 없고 정확히 연결과 끊어주기만 하면 됨

 

1. 새로운 노드 생성

2. pointer 기준 좌측 노드의 참조값을 새로운 노드의 left 변수에 저장

3. pointer 기준 좌측 노드에 새로운 노드의 참조값을 right 변수에 저장

4. pointer가 가리키는 노드의 참조값을 새로운 노드의 right 변수에 저장

5. pointer가 가리키는 노드에 새로운 노드의 참조값을 left 변수에 저장

 

 

 

---

3. 이중 연결 리스트 삭제

1) 노드가 한 개인 경우

head와 tail에 null 값을 저장하면 자연스럽게 연결리 끊어져 가비지 컬렉터의 스케줄링에 의해 제거됨

 

 

 

---

2) 맨 앞의 노드 삭제

1. 삭제할 노드의 우측 노드의 left 변수에 null 값 저장

2. 삭제할 노드의 right 변수에 null 값 저장

3. head에 삭제할 노드의 우측 노드 저장

* 자바 같은 경우 삭제될 노드의 이전 노드, 다음 노드, 데이터를 null로 변경시키지 않아도 GC의 수집 대상이 되며 GC 스케줄러에 의해 소멸됨

BUT 가비지 컬렉터가 존재하지 않고 직접 메모리를 관리해야 하는 언어는 직접 메모리를 해제시켜줘야 함.

여기서 null 값으로 변경하는 이유는 단지 명시적으로 설명하기 위함임!!

 

 

---

3) 맨 뒤의 노드 삭제

1. 삭제할 노드의 좌측 노드의 right 변수에 null 값 저장

2. 삭제할 노드의 left 변수에 null 값 저장

3. tail에 삭제할 노드의 좌측 노드 저장

 

 

 

---

4) 중간의 노드 삭제

0. pointer 기준 좌측 노드와 우측 노드의 참조값 미리 저장

=> 좌/우측 노드의 참조값을 임시 변수에 저장하면 연결 순서는 크게 상관 없고 정확히 연결과 끊어주기만 하면 됨

 

1. pointer 기준 좌측 노드의 right 변수에 pointer 기준 우측 노드의 참조값을 저장

2. pointer 기준 우측 노드의 left 변수에 pointer 기준 좌측 노드의 참조값을 저장

3. 삭제할 노드의 left 변수와 right 변수에 null 값 저장

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼