이중 연결 리스트(Doubly Linked List)

이중 연결 리스트란?(What is Doubly linked list?)

---

이중 연결 리스트(doubly linked list)는 기존 단순, 원형 연결 리스트의 단점인 단방향 흐름을 2개의 링크 필드를 이용하여 양방향으로 움직일 수 있게 만든 것이 이중 연결 리스트이다. 원형 연결 리스트에 이중 연결 리스트를 결합하면 이중 원형 연결 리스트가 된다. 이중 연결 리스트는 양방향으로 움직일 수 있어 데이터 접근이 단순, 원형 연결 리스트보다 쉽고 삽입, 삭제 연산시 선행 노드에 대한 정보가 필요없다는 장점이 있다. 이중 연결 리스트의 노드는 다음과 같다.

 

이중 연결 리스트의 노드

이중 연결 리스트

 

이중 연결 리스트의 기본적인 연산은 다음과 같다.

1. 리스트 생성
2. 노드 삽입
3. 노드 삭제

 

리스트 생성

리스트는 헤드 노드를 갖는 리스트를 생성한다. 리스트를 생성하면 왼쪽 링크와 오른쪽 링크를 모두 NULL로 만들어 준다.

헤드 노드를 갖는 리스트 생성

노드 삽입

첫번째 노드 삽입

첫번째 노드 삽입의 경우, 새로운 노드를 생성한 후 새로운 노드의 오른쪽 링크는 변경전 첫번째 노드를 가리키고 변경 전 첫번째 노드의 왼쪽 링크는 새로운 노드를 가리키게 한다. 그후 헤드 노드의 오른쪽 노드가 새로운 노드를 가리키도록 한다.

 

1. 새로운 노드 생성

 

2. 새로운 노드와 data1 연결(새로운 노드의 오른쪽 링크)

 

 

3. 새로운 노드와 data1 연결(data1노드의 왼쪽 링크)

 

4. 헤드노드와 새로운 노드 연결(헤드 노드의 오른쪽 링크)

 

 

마지막 노드 삽입

마지막 노드 삽입은 새로운 노드의 오른쪽 링크는 NULL을, 왼쪽 링크는 변경전 마지막 노드를 가리키도록 한다. 변경전 마지막 노드의 오른쪽 링크는 새로운 노드를 가리키도록 한다.

 

 

1. 새로운 노드 생성

 

2. 새로운 노드와 data2노드 연결(새로운 노드의 왼쪽 링크)

 

 

3. 새로운 노드와 data2노드 연결(data2 노드의 오른쪽 링크)

 

중간 노드 삽입

중간 노드 삽입은 글로 설명하는 것보다 그림으로 설명하는 것이 보기 편하기 때문에 설명글은 생략한다.

 

1. 새로운 노드 생성

 

 

2. 새로운 노드와 data2노드 연걸(새로운 노드의 오른쪽 링크)

 

 

3. 새로운 노드와 data1노드 연결(data1노드의 오른쪽 링크)

 

 

4. 새로운 노드와 data2노드 연결(data2노드의 왼쪽 링크)

 

 

5. 새로운 노드와 data1노드 연결(새로운 노드의 왼쪽 링크)

 

노드 삭제

여기서 노드 삭제는 중간 노드 삭제만 다루겠다. 중간 노드의 삭제는 다른 변수 필요없이 삭제되는 노드 자신을 가지고 연결을 한다. 먼저 삭제되는 노드의 왼쪽 노드의 오른쪽 링크를 삭제되는 노드의 다음 노드를 가리키도록 한다. 그후 삭제되는 노드의 오른쪽 노드의 왼쪽 링크가 삭제되는 노드의 이전 노드를 가리키게 한다. 그후 노드를 삭제한다.

 

 

 

1. ptr로 삭제할 노드 지정

 

 

 

2. data1노드와 data2노드 상호 연결

 

 

3. ptr노드 삭제

 

이중 연결 리스트의 구현

---

구현은 아래 필자의 깃허브에 있으니 참고하길 바란다. 기본적인 원리만 구현을 했기 때문에 실제 사용에는 무리가 있다.참고만 하길 바란다.

GitHub - LimeTree0/Data-Structure