연결 자료구조와 연결 리스트(2)

이중 연결 리스트(뒤로 가기가 가능한 리스트)

이중 연결 리스트는 양방향 연결을 지원하는 리스트입니다. 각 노드가 다음 노드를 가리키는 포인터(rlink, right link)뿐만 아니라, 이전 노드를 가리키는 포인터(llink, left link)까지 함께 가지고 있습니다.

 이 차이로 특정 노드를 기준으로 앞뒤를 자유롭게 탐색할 수 있어 단순 연결 리스트에서는 비효율적이었던 '특정 노드 삭제'나 '역순 탐색' 같은 작업이 매우 간단하고 빨라집니다.

• 삽입 연산 : 새 노드를 중간에 삽입할 때, 새 노드와 그 앞뒤 노드 간의 관계를 모두 설정해야 합니다. 총 4개의 링크(포인터)를 조작하여 양방향 연결을 완성합니다.
• 삭제 연산 : 중간의 노드를 삭제할 때, 삭제할 노드의 앞 노드와 뒤 노드가 서로를 직접 가리키도록 두 개의 링크만 수정해주면 됩니다.

원형 이중 연결 리스트

원형 이중 연결 리스트는 이중 연결 리스트의 양 끝을 서로 연결하여 순환하는 구조로 만들어집니다. 이 구조의 핵심은 더미 노드(Dummy Node)의 존재입니다.

 더미 노드는 실제 데이터를 저장하지 않는 가짜 노드로, 리스트의 시작점과 끝점 역할을 합니다. 모든 연산은 이 더미 노드를 기준으로 이루어집니다.

• 더미 노드의 장점 : 리스트가 비어있을 때, 혹은 리스트의 맨 앞이나 맨 뒤에 데이터를 추가/삭제할 때 발생하는 까다로운 예외 상황을 처리할 필요가 없어집니다. 모든 삽입/삭제 연산이 '리스트 중간에서의 연산'과 동일한 로직으로 단순화되어 코드의 안정성과 가독성이 크게 향상됩니다.