[자료구조] 8강 동적 연결된 스택과 큐~ 연결리스트

동적 연결된 스택과 큐

 

순차 표현방법은 스택이나 큐가 하나만 있을 때는 효율적이나 여러 개의 스택이나 큐가 동시에 있을 때 이들을 순차적으로 표현할 효율적인 방법이 X , 이 경우에는 연결 리스ㅡ로 표현을 하여 스택은 top pointer로 첫 번 째 노드를 가리키게 하고, 큐의 경우에는 첫 번째와 마지막 노드를 front와 rear pointer가 가리킴으로써 삽입/삭제가 가능하도록 할 수 있다.

 

비사용 기억 공간

 

1. 순차 가용 공간에서의 노드 획득

2. 초기 가용 공간에서의 연결 리스트 생성

3. 연결 리스트 가용 공간에서의 노드 획득

4. 연결 리스트로 된 가용 공간에 삭제 노드의 반환

 

연결 리스트의 응용

 

1. 다항식의 단순 연결 리스트 표현

2. 다항식의 덧셈

3. 단순 연결 리스트로 표현된 다항식의 노드 반환

4. 다항식의 원형 연결 리스트 표현

 

연결 리스트의 기타 연산

 

1. 단순 연결리스트의 역순

- 단순 연결 리스트는 리스트를 구성하는 노드들이 한쪽 방향으로 연결된 구조를 의미하며 삽입과 삭제가 용이하고 기억장소를 낭비하지 않는 장점을 가진다.

리스트를 역순으로 만드는 과정은 많은 작업량을 가지므로 이러한 리스트를 역순으로 만들기 위해서는 리스트의 각 노드들이 선행 노드와 후속 노드를 지정할 수 있는 원형 연결 리스트 또는 이중 원형 연결 리스트로 표현하는 것이 효율적

2. 단순 연결 리스트의 연결

3. 원형 연결 리스트의 앞 또는 뒤에 노드 삽입

4. 원형 연결 리스트의 길이 계산

 

이중 연결 리스트

 

1. 필요성 : 단순 연결 리스트는 선행 노드를 찾기 힘들고 삽입이나 삭제할 때 반드시 선행노드가 필요하고 리스트의 연결 방향으로만 탐색이 가능하므로 역으로 탐색하는 것이 불가능하다. 따라서 양방향으로의 탐색이 가능하도록 두 개의 링크 필드를 갖는 노드로 구성한 리스트를 이중 연결 리스트라고 하며, 임의의 노드의 후속 노드뿐만 아니라 선행 노드를 탐색할 수 있는 리스트이다.

2. 정의 : 이중 연결 리스트는 2개의 링크를 가지는 노드로 구성

3. 노드 삭제 : 이중 연결 리스트에서 노드 삭제는 삭제할 노드의 오른쪽 노드의 주소를 삭제 노드의 왼쪽 노드의 rlink로 저장하고 삭제 노드의 왼쪽 노드의 주소를 삭제 노드의 오른쪽 노드의 link로 정정한 후 삭제노드를 해제한다.

4. 노드 삽입 : 순서대로 링크값을 정정하면 노드의 삽입이 이루어진다.

 

일반 리스트

1. 정의 : 일반 리스트는 0개 이상의 원소 또는 서브 리스트를 가지는 유한 순차 리스트이다.

2. 다중 변수 다항식의 일반 리스트 표현

3. 태그 필드를 이용한 다중 변수 다항식의 일반 리스트 표현