[ 자료구조 및 알고리즘 ] 5.연결 자료구조 -4. 이중 연결 리스트

이중 연결 리스트(doubly linked list)

양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트

 

이중 연결 리스트의 노드 구조

• 두 개의 링크 필드와 한 개의 데이터 필드로 구성
• llink(left link) 필드 : 왼쪽노드와 연결하는 포인터
• rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터

• 노드 구조에 대한 구조체 정의

ypedef struct Dnode{
	struct Dnode *llink;
	char data[5];
	struct Dnode *rlink;
} ;

 

리스트 week=(월, 수, 금)의 이중 연결 리스트 구성

 

원형 이중 연결 리스트

• 이중 연결 리스트를 원형으로 구성

 

이중 연결 리스트에서의 삽입 연산 

이중 연결 리스트에서의 삽입 연산 과정

❶ 삽입할 노드를 가져온다.
❷ 새 노드의 데이터 필드에 값을 저장한다.
❸ 새 노드의 왼쪽 노드(new.llink)의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장한다.
❹ 그리고 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드의 주소를 저장한다.
❺ 새 노드의 오른쪽 노드(new.rlink)의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 저장한다.
❻ 그리고 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장한다.

이중 연결 리스트에서의 삽입 알고리즘

이중 연결 리스트 DL에서 포인터 pre가 가리키는 노드의 다음 노드로 노드 new를 삽입하는 과정

❶ new.rlink ← pre.rlink ;

• 노드 pre의 rlink를 노드 new의 rlink에 저장하여, 노드 pre의 오른쪽 노 드를 삽입할 노드 new의 오른쪽 노드로 연결

❷ pre.rlink ← new;

• 새 노드 new의 주소를 노드 pre의 rlink에 저장하여, 노드 new를 노드 pre의 오른쪽 노드로 연결

❸ new.llink ← pre;

• 포인터 pre의 값을 삽입할 노드 new의 llink에 저장하여, 노드 pre를 노 드 new의 왼쪽노드로 연결

❹ new.rlink.llink ← new;

• 포인터 new의 값을 노드 new의 오른쪽노드(new.rlink)의 llink에 저장하 여, 노드 new의 오른쪽노드의 왼쪽노드로 노드 new를 연결

 

양방향 기차 사람 나가기

 

 

 

 

이중 연결 리스트에서의 삭제 연산 

이중 연결 리스트에서의 삭제 연산 과정

❶ 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크(rlink)에 저장한다.

❷ 삭제할 노드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장한다.

❸ 삭제한 노드를 자유공간리스트에 반환한다.

 

이중 연결 리스트에서의 삭제 알고리즘

이중 연결 리스트 DL에서 포인터 old가 가리키는 노드를 삭제하는 과정 

• 초기 상태

❶ old.llink.rlink ← old.rlink;

• 삭제할 노드 old의 오른쪽노드의 주소를 노드 old의 왼쪽노드의 rlink에 저장하여, 노드 old의 오른쪽노드를 노드 old의 왼쪽노드의 오른쪽노드 로 연결

❷ old.rlink.llink ← old.llink;

• 삭제할 노드 old의 왼쪽노드의 주소를 노드 old의 오른쪽노드의 llink에 저장하여, 노드 old의 왼쪽노드를 노드 old의 오른쪽노드의 왼쪽노드로 연결

❸ returnNode(old);
• 삭제된 노드 old는 자유공간리스트에 반환