[자료구조] chap7. 연결리스트 II

7.1 원형 연결 리스트

• 원형 연결 리스트 : 마지막 노드가 첫 번째 노드 가리키는 리스트(마지막 노드의 링크필드가 null이 아닌 첫번째 노드 주소가 되는 리스트) 
  • 장점: 하나의 노드에서 다른 모든 노드로의 접근 가능 - 링크 계속 따라가면 결국 모든 노드 거쳐서 자기 자신으로 되돌아온다. ->노드 삽입,삭제가 단순 연결리스트보다 용이.(삭제나 삽입시 항상 선행노드 가리키는 포인터 필요)

 

• 특히 유용한 경우 : 리스트의 끝에 노드 삽입하는 연산이 단순 연결리스트보다 효율적. (단순 연결리스트에서 리스트 끝에 노드 추가하려면 첫 번째 노드에서부터 링크를 따라서 노드의 개수만큼 진행하여 마지막 노드까지 가야함.)

마지막 노드는 헤드포인터인 head가 가리키고 있고, 첫번째 노드는 head->link가 가리키고 있음 -> 리스트의 마지막에 노드를 삽입하거나 삭제하기 위해 리스트의 맨 끝까지 안 가도 됨.

 

• 원형연결리스트는 원칙적으로 헤드 포인터만 있으면 된다.

 

 

 

• 원형리스트의 처음에 삽입 : 새로운 노드의 링크인 node->link 가 첫번째 노드를 가리키게 하고 다음에 마지막 노드의 링크가 node를 가리키게 하면 된다. head(헤드포인터)가 마지막 노드 가리키는 것 기억!

 

• 원형리스트의 끝에 삽입 : 어디가 처음이고 끝인지 불분명 ->head의 위치만 새로운 노드로 바꾸어주면 새로운 노드가 마지막 노드가 된다.

 

* 마지막 노드의 링크가 NULL이 아니기 때문에 리스트의 끝에 도달했는지 검사하려면 헤드포인터와 비교해야 한다. while 루프 대신 do-while 루프를 써야 한다.

 

7.2 원형 연결 리스트는 어디에 사용될까?

1. 컴퓨터에서 여러 응용 프로그램을 하나의 CPU를 이용하여 실행할 때 필요 - 현재 실행중인 모든 응용 프로그램은 원형 연결 리스트에 보관됨, 운영체제는 원형 연결 리스트에 있는 프로그램의 실행을 위해 고정된 시간 슬롯 제공. 운영체제는 모든 응용프로그램이 완료될때까지 원형연결리스트를 계속 순회.

2. 멀티플레이어게임 ; 모든 플레이어는 원형연결리스트에 저장, 한 플레이어의 기회가 끝나면 포인터 앞으로 움직여서 다음 플레이어의 순서가 된다.

 

3. 원형큐 만들 때 사용 : 배열뿐만 아니라 원형 연결 리스트를 이용하여 원형 큐를 구현할 수 있다. (2개의 포인터 : front, rear 가 있어야 함.)

 

 

7.3 이중연결리스트

 

• 단순연결리스트의 어떤 노드에서 후속노드를 찾기 쉽지만 선행노드를 찾으려면 어렵다. (원형연결리스트도 마찬가지.)
  • -> 특정 노드에서 양방향으로 자유롭게 움직일 필요가 있다면 단순연결리스트구조 부적합.
• 이중연결리스트: 하나의 노드가 선행노드와 후속노드에 대한 두 개의 링크를 갖는 리스트. 링크가 양방향이어서 양방향으로 검색 가능 (단점: 공간 많이 차지하고 코드 복잡)

• 실제로는 이중연결리스트와 원형연결리스트 혼합한 형태가 많이 사용. 
• 헤드 노드(데이터필드에 아무 정보 x, 다만 삽입과 삭제 알고리즘 간편하게 하기 위해 존재)라는 특별한 노드 추가하는 경우 많음(헤드포인터-리스트의 첫번째 노드 가리키는 포인터 와 구분!) 

3개의 필드 : 왼쪽링크필드-data필드-오른쪽링크필드 *링크필드는 포인터로 이루어짐

 

이중연결리스트에서 임의의 노드 가리키는 포인터를 p라 하면 다음 관계 성립.

앞뒤로 똑같이 이동할 수 있음

위 관계는 공백리스트에서도 성립(헤드노드 존재)

 

• 삽입연산 : 링크필드 값 바꾸기. 새로 만들어진 노드의 링크를 먼저 바꿈 > 새로 만들어진 노드 링크는 아무런 정보 갖고있지 않아서 변경해도 안전

*이중연결리스트는 보통 헤드 노드가 존재하므로 얘만 있으면 단순 연결리스트처럼 헤드포인터가 필요 없다.(헤드노드만 알고 있으면 어떤 노드로도 접근 가능-main함수 안에 변수로 head라는 이름으로 생성돼 있음(포인터변수가 아니라 구조체 변수임!!유의)

*사용하기 전에 반드시 초기화해야함 - 헤더노드의 링크필드들이 자기 자신을 가리키도록

 

7.4 연결리스트로 구현한 스택

 

• 스택은 배열뿐만 아니라 연결리스트 이용해서도 구현될 수 있음.(연결된 스택 이라 함)

• 연결된 스택 : 외부에서 보기에는 배열을 이용하나 연결리스트 이용하나 차이x. 스택의 내부구현만 달라짐.                >>연결리스트 사용해 스택 만들면 크기 제한 x ( 동적메모리 할당만 할 수 있으면 스택에 새로운 요소 삽입 가능) but 동적메모리 할당이나 해제 해야하므로 삽입이나 삭제시간 좀 더 걸림.
• 삽입연산: 연결된 스택은 개념적으로 단순 연결리스트에서 맨 앞에 데이터 삽입하는 것과 동일

삭제연산 시 링크필드 변화 나와있음

• 삭제연산: top의 값을 top->link로 바꾸고 기존의 top이 가리키는 노드를 동적메모리해제하면 됨
• 연결된 스택
  • 공백상태: 연결리스트와 마찬가지로 top포인터가 NULL인 경우
  • 포화상태: 동적메모리할당만 된다면 노드를 생성할 수 있어서 없는 거나 마찬가지

 

7.5 연결리스트로 구현한 큐

• 연결된 큐 : 연결리스트로 만들어진 큐
  • 장 : 배열로 구현된 큐에 비해 크기 제한 X
  • 단 : 배열로 구현된 큐에 비해 코드 약간 더 복잡, 링크 필드때문에 메모리공간 더 많이 사용
  • 기본적 구조: 단순 연결리스트에 2개의 포인터 추가한 것. front 포인터는 삭제와 관련, rear 포인터는 삽입과 관련. 큐에 요소 없는 경우 front와 rear은 NULL값 됨. 큐의 요소들은 구조체로 정의, 이 구조체는 데이터 저장하는 data 필드와 다음 노드 가리키기 위한 포인터 들어있는 link 필드로 이루어짐

 

• 삽입연산 : 동적메모리 할당 통해 새로운 노드 생성 > 데이터 저장> 연결리스트 끝에 새로운 노드 추가 (큐가 공백상태이면 (front, rear값 모두 NULL) front와 rear 모두 새로운 노드 가리키도록 해야함, 기존 노드 있는 경우에는 rear가 가리키는 노드 링크 필드, rear을 새로운 노드 가리키도록 변경)

• 삭제연산 : 연결리스트의 처음에서 노드 꺼내오면 됨. 큐가 공백상태인지 검사>공백상태라면 오류>오류이면 오류메시지 출력하고 종료. 공백상태가 아니면 front가 가리키는 노드를 temp가 가리키도록 하고 front는 front의 링크값으로 대입. > front는 현재 가리키는 노드의 다음 노드를 가리킴 > temp가 가리키는 노드로부터 데이터 꺼내옴 > 동적메모리 리 해제 통해 이 노드 삭제