자료구조 프로그래밍15 연결리스트의 다양한 구현 원형연결리스트에서 마지막 노드의 링크는 다른 노드들의 링크와 의미가 다르기 때문에 마지막 노드임을 나타내는 정보를 유지하는 것이 필요하다. 원형연결리스트는 첫번째 노드에 대한 포인터 대신 마지막 노드에 대한 포인터(clist)를 이용해서 나타내는 것이 일반적이다. 이와 같이 하면, 원형연결리스트의 첫 번째 노드는 항상 마지막 노드(clist 노드)의 링크를 통해 접근할 수 있다. 첫 번째 노드로 추가되는 경우에는 노드포인터 clist가 나타내는 마지막 노드의 링크가 변경되는 반면에 마지막 노드로 추가되는 경우에는 노드포인터 clist 자체가 변경된다. 이중연결리스트에도 원형연결리스트의 개념을 사용할 수 있다. 이중연결리스트에서 원형연결리스트 개념을 사용한 것을 이중원형연결리스트(doubley circul.. 2024. 3. 16. 순서리스트의 연결표현(3) 3.3.2 이중연결리스트 연결리스트에서는 각 노드의 링크를 이용해서 직후노드와 그 이후 순서의 노드들을 간단하게 탐색할 수 있지만 직전 노드 또는 그 이전 순서의 노드들을 탐색할 때는 많은 시간이 걸린다. 특히 연결리스트의 노드들을 역순으로 처리해야 하거나 각 노드의 앞쪽 노드들을 탐색해서 처리해야 하는 경우 연결리스트는 많은 처리시간을 필요로 해서 비효율적이게 된다. 이런 문제는 각 노드에 링크를 2개씩 유지해서 한 링크는 직후 노드에 대한 위치정보를 저장하고, 다른 한 링크는 직전노드에 대한 위치정보를 저장하면 해결할 수 있는데, 이와 같이 각 노드에 각각 직전노드와 직후노드에 대한 두 링크를 유지하는 연결리스틀르 이중연결리스트(doubly linked list)라고 한다. 이중연결리스트와 대응해서 .. 2024. 3. 16. 순서리스트의 연결표현(2) (2) current 변수가 NULL인 경우 이 경우는 추가원소의 직전노드가 없는 경우로, 추가노드는 연결리스트의 첫 번째 노드로 추가된다. 추가원소가 연결리스트의 첫 번째 노드가 된다면, 연결리스트의 첫 번째 노드를 나타내는 노드포인터(예를 들면, first)를 변경해야 하는데, 이것은 current 노드의 직후노드로 추가할 때 추가노드를 current 노드의 링크에 연결하는 대신 첫 번째 노드포인터 변수 first에 연결하는것과 같게 된다. 추가원소 x를 연결리스트의 첫 번째 노드로 추가할 때는 추가원소를 위한 노드를 생성한 후(temp 노드), 순차적으로 first 노드(노드포인터 first가 나타내는 노드)를 temp 노드의 링크에 연결하고, 노드포인터 first가 temp 노드를 나타내도록 하면.. 2024. 3. 16. 순서리스트의 연결표현(1) 연결리스트에서는 첫 번째 노드를 제외한 모든 노드들은 항상 그 직전노드의 링크를 통해 접근된다. 일반적으로 연결리스트의 노드 추가함수를 설계할 때는 insertLinkedList(L, current, x)와 같이 추가원소의 직전노드를 나타내는 노드포인터 변수 current를 형식인수로 정의해서 추가노드를 current 노드의 다음으로 추가하고, 삭제함수를 정의할 때도 위의 deleteLinkedlist(L, current)와 같이 삭제할 노드의 직전노드를 나타내는 노드포인터 변수 current를 형식인수로 정의해서 current 노드의 다음 노드를 삭제한다. 추가노드나 삭제노드의 직전노드를 형식인수로 정의하지 않으면, 함수 내부에서 그 직전노드를 탐색해서 처리해야 하는데, 이것은 그만큼 함수의 코드를 복.. 2024. 3. 16. 이전 1 2 3 4 다음