원형 연결 리스트와 이중 연결 리스트
| 단순 연결 리스트 | 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가지며 연결 리스트, 선형 연결 리스트, 단순 연결 선형 리스트라고도 한다. |
| 원형 연결 리스트 | 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형을 만든 연결 리스트이다. |
| 이중 연결 리스트 | 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트로 이중 연결 리스트는 왼쪽 노드, 연결하는 포인터, 오른쪽 노드를 연결하는 포인터 2개가 필요하다. |
원형 연결 리스트의 개념
단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키에 하여 리스트의 구조를 원형으로 만든 연결 리스트
○ 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성
○ 링크를 따라 계속 순회하면 이전 노드에 접근 가능
원형 연결 리스트의 알고리즘
원형 연결 리스트 첫 번째 노드로 삽입하는 과정
삽입하는 노드 new는 리스트의 첫 번째 노드이자 마지막 노드가 되어야 함
① if (CL=NULL); 공백 리스트인 경우
①-ⓐ CL ← new; 포인터 CL이 노드 new를 가리키게 함
①-ⓑ new.link ← new; 노드 new가 자기 자신을 가리키게 함으로써 노드 new를 첫 번째 노드이자 마지막 노드가 되도록 지정
② else 공백 리스트가 아닌 경우
②-ⓐ temp ← CL; 리스트가 공백리스트가 아닌 경우에는 첫 번째 노드의 주소를 임시 순회 포인터 temp에 저장하여 노드 순회의 시작점을 지정
②-ⓑ temp ← temp.link; while 문을 수행해 순회 포인터 temp를 링크를 따라 마지막 노드까지 이동
②-ⓒ new.link ← temp.link; 리스트의 마지막 노드의 링크 값을 노드 new의 링크에 저장하여 노드 new는 노드 temp의 다음 노드인 첫 번째 노드와 연결
②-ⓓ temp.link ← new; 포인터 new의 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장하여, 리스트의 마지막 노드가 노드 new를 가리키게 한다.
②-ⓔ CL ← new; 노드 new의 값을 리스트 포인터 CL에 저장하여 노드 new가 리스트의 첫 번째 노드가 되도록 지정
리스트 중간에 노드를 삽입하는 알고리즘
① 공백 리스트인 경우
② 공백 리스트가 아닌 경우
②-ⓐ new.link ← pre.link; 노드 pre의 다음 노드로 new를 삽입하기 위해서, 먼저 노드 pre의 다음 노드(pre.link)를 new의 다음 노드(new.link)로 연결
②-ⓑ pre.link ← new; 노드 new의 값(삽입할 노드의 주소)을 노드 pre의 링크에 저장하여, 노드 pre가 노드 new를 가리키도록 함
노드 삭제 알고리즘
① old → pre.link; 노드 pre의 다음 노드(pre.link)를 삭제할 노드 old로 지정
② pre.link → old.link; old의 다음노드(old.link)를 노드 old의 이전노드 pre 노드와 서로 연결
③ if(old=CL) then 삭제할 노드 old가 원형 연결 리스트의 첫 번째 노드인 경우
③-ⓐ CL←old.link; 첫 번째 노드를 삭제하는 경우에는 노드 old의 링크 값을 리스트 포인터 CL에 저장하여 두 번째 노드가 리스트의 첫 번째 노드가 되도록 조정
④ returnNode(old); 삭제한 노드 old의 메모리를 반환함
이중 연결 리스트
양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
이중 연결 리스트의 노드 구조와 구조체 정의
Llink(left link) 필드
왼쪽 노드와 연결하는 포인터
rlink(right link) 필드
오른쪽 노드와 연결하는 포인터
(b)의 양방향 기차를 이중 연결 리스트라고 생각하면
왼손의 이름표는 llink, 오른손의 이름표는 rlink
이중 연결 리스트에 노드를 삽입
이중 연결 리스트에서 노드를 삽입하는 방법
1. 삽입할 노드를 준비한다.
2. 새 노드의 데이터 필드에 값을 저장한다.
3. 새 노드 왼쪽 노드의 오른쪽 링크 필드(rlink)에 있던 값을 새 노드의 오른쪽 링크 필드(rlink)에 저장한다.
4. 왼쪽 노드의 오른쪽 링크 필드(rlink)에 새 노드의 주소를 저장한다.
5. 새 노드 오른쪽 노드의 왼쪽 링크 필드(llink)에 있던 값을 새 노드의 왼쪽 링크 필드(llink)에 저장한다.
6. 오른쪽 노드의 왼쪽 링크 필드(llink)에 새 노드의 주소를 저장한다.
7. 노드를 순서대로 연결한다.
이중 연결 리스트에 노드를 삽입하는 알고리즘
이중 연결 리스트에 노드를 삽입하는 과정
데이터 필드값이 x인 노드 new를 준비, 포인터 pre가 가리키는 노드의 다음 노드로 삽입하려고 한다고 가정
① new.rlink ← pre.rlink;
② pre.rilnk ← new;
③ new.llink ← pre;
④ new.rlink.link ← new;
이중 연결 리스트에 노드를 삭제하는 알고리즘
이중 연결 리스트에서 노드를 삭제하는 방법
1. 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 찾는다.
2. 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크 필드(rilnk)에 저장한다.
3. 삭제할 노드의 왼쪽 노드(old.llink)의 주소를 삭제할 노드의 오른쪽 노드(old.rilnk)의 왼쪽 링크 필드에 저장한다.
4. 노드를 순서대로 연결한다.
① old.link.rlink ← old.rlink;
② old.rlink.llink ← old.llink;
③ returnNode(old);
