[데이터 구조] 11차시 연결 데이터 표현 | 자유 공간 리스트, 원형 연결 리스트, 이중 연결 리스트

모듈1. 자유 공간 리스트

1) 메모리의 획득과 반납 방법

(1) 연결 리스트가 필요로 하는 두 가지 연산

• [방법 1] : 데이터 필드와 링크 필드를 가진 하나의 공백 노드를 획득하는 방법
  (프로그램 수행 중, 즉석에서 필요한 메모리를 OS에서 malloc()하는 방식)
  
  
• [방법 2] : 사용하지 않는 노드는 다시 반납하여 재사용하는 방법
  (미리 malloc()하여 free space list를 만든 후, 여기서 할당/회수하는 방식)

 

(2) [방법 2] 자유 공간 리스트(free space list)를 만들어 놓은 경우 - OS와 분리를 해보자!

• 추가로 우리가 만들어야 하는 함수1 : getNode() - malloc() 대응
  : 데이터와 링크 필드로 되어 있는 새로운 공백 노드를 free space list로부터 할당 받아 그 주소를 반환하는 함수를 만들어 유지
  
  
• 추가로 우리가 만들어야 하는 함수2 : returnNode(p) - free() 대응
  - 포인터 변수 p가 지시하는 노드를 free space list에 반환하는 함수를 만들어 유지
  - 프로그래밍 언어에 따라 필요한 경우도 있고 필요하지 않은 경우도 있음
  - Java와 같이 쓰레기 수집기(garbage collector)가 있는 언어에서는 사용자가 직접 관리할 필요가 있는 경우에 사용

 

2) 자유 공간 리스트

- 필요에 따라 요구한 노드를 할당할 수 있는 자유 메모리 풀

- 자유 공간 관리를 위해 연결리스트 구조를 이용하기 위해서는 초기에 사용할 수 있는 메모리를 연결 리스트로 만들어 놓아야 함(while로 malloc()을 많이 해두는 것)

 

 

- 노드 할당 요청을 받으면 자유 공간 리스트 앞에서부터 공백 노드를 할당

 

 

3) 노드 할당

• 새로운 노드를 할당하는 함수 : getNode()
  - Free 포인터가 가리키는 빈 노드 하나를 newNode에게 준다.

 

 

• 노드를 할당한 뒤의 자유 공간 리스트

 

• 자유 공간을 모두 할당해 주고, 더 이상 Free가 없는 경우
  - 사용하지 않는 노드들을 자유 공간 리스트에 반환함
  - 시스템이 자동으로 모든 노드들을 검사하여, 사용하지 않는 노드들을 자유 공간 리스트의 노드로 만듦
  ▶️ Free에 빈 노드가 생기면, 그때 다시 노드 할당 작업을 재개(garbage collection)

 

 

4) 노드 반환

• 삭제된 노드 p를 자유 공간 리스트에 반환

 

• 반환된 노드가 자유 공간 리스트에 삽입되는 과정

 

 

 

 

모듈2. 원형 연결 리스트

1) 원형 연결 리스트(circular linked list)

• 마지막 노드의 링크가 다시 첫 번째 노드를 가리키는 리스트
• 한 노드에서 다른 어떤 노드로도 접근할 수 있음
• 리스트 전체를 자유 공간 리스트에 반환할 때 리스트의 길이에 관계 없이 일정 시간에 반환할 수 있음

 

 

 

2) 원형 연결 리스트 연산

(1) 원형 연결 리스트를 자유 공간 리스트에 반환

returnCList(C) // C 포인터가 이끄는 원형 리스트를 받는다
			// 원형 연결 리스트 C를 자유 공간 리스트에 반환
	if (C=null) then return;	// C가 빈 list이면 종료, 그렇지 않으면 계속함
    p <- C.link;	// (1) p 설정
    C.link <- Free;	// (2) Free 포인터가 이끄는 빈 공간 List를 C.link에 연결
    Free <- p;		// (3) p가 이끄는 새로운 원형 리스트를 Free가 가리킨다.

end returnCList()

 

 

 

(2) C pointer가 가리키는 원형 리스트에서의 노드 삽입

C.link = p; -> O(1)

 

 

(3) 리스트의 첫 번째 노드로 삽입하는 알고리즘

insertFront(C, p)
					// C는 원형 리스트의 마지막 노드, p는 삽입할 노드를 지시
	if(C=null) then {		// C에 아무 노드가 없는 상태
    	C <- p;				// 아무것도 없으니, 삽입해야 하는 p를 C로 설정함
        p.link <- C;		// 어차피 1개이지만, 그래도 p의 link field에 주소를 넣어주는 의미임
    }
    else {
    	p.link <- C.link;	// 아래의 (1)번
        C.link <- p;		// 아래의 (2)번
        ***	// 만약, 마지막에 노드를 삽입하는 경우는 ***에 C <- p;를 넣으면 됨
    }
end insertFront()

 

 

 

(4) 리스트의 길이 계산

lengthC(C)	// 원형 리스트 C의 길이 계산
    if(C = null) then return 0;
    
    length <- 1;	// length 변수로 count함
    p <- C.link;	// (1) p는 순회 포인터로 정의하고, C 다음을 지칭하게 함
    
    while(p != C) do {	// p가 처음 출발한 위치(C)로 되돌아 왔는지 검사
    	length <- length + 1;	// length를 하나 증가시킴
        p <- p.link;			// p를 전진시킴
    }
    return length;
end lengthC()

 

 

 

모듈3. 이중 연결 리스트

1) 이중 연결 리스트

• 단순 연결 리스트나 원형 연결 리스트의 문제점
  : 어떤 노드 p에서 이 p의 선행자를 찾기가 어려움
• 이중 연결 리스트(doubly linked list)
  - 노드는 data, llink(왼쪽 링크), rlink(오른쪽 링크) 필드를 가짐
  - 리스트는 선형이 될 수도 있고 원형이 될 수도 있음
  
  
• 이중 연결리스트를 C로 구현하기 위한 struct doubleListNode 타입

typedef 뒤에 struct 있는걸로 생각

 

 

트리 구조에 사

 

• 이중 연결 리스트 참고
  - 리스트는 선형이 될 수도 있고(아래의 a), 원형이 될 수도 있음(아래의 b)
  - p = p.llink.rlink = p.rlink.llink(모두 p 스스로를 나타내는 표현)

 

 

2) 이중 연결 리스트 연산

- 이중 연결 리스트에서의 노드 삭제/삽입