[자료구조] 6강 - 연결 리스트의 응용

✅ 1. 연결 리스트의 변형

(1) 단순 연결 리스트의 문제점

• 단순 연결 리스트는 하나의 링크만 있고, 각각의 노드의 링크는 후행 노드만을 가리키는 구조이다.
• 즉, 특정 노드의 후행 노드는 쉽게 접근할 수 있지만, 특정 노드의 선행 노드에 대한 접근은 헤드 노드부터 재검색을 해야 하는 문제가 있음. 이것을 해결하기 위해 연결 리스트를 변형한 형태가 만들어짐.
• 연결 리스트 변형은 위이미지와 같이 이중 연결 리스트, 단순 원형 연결 리스트가 될 수 있음.

(2) 이중 연결 리스트란?

• 기존 단순 연결 리스트는 후행 노드만을 가리키는 link 만 있음.
• 이중 연결 리스트는 두 개의 link 를 가지고 있으며 각각 선행 노드, 후행 노드의 링크를 가지고 있게 됨.
• 결과적으로 후행 노드를 가리킬 수 있어, 소스 코드가 간단해지고 효율이 올라갈 수 있는 장점이 있음.
• 다만, link 주소를 2개를 가지고 있기 때문에 그만큼 메모리 공간을 차지하게 된다는 단점이 있음.

(3) 원형 연결 리스트란?

• 마지막 원소의 link 값을 특정 위치의 link 주소값으로 넣은 리스트를 의미함. 즉, 원형으로 돌게되는 순환 구조가 만들어짐.
• 단순 연결 리스트를 살펴보면, 가장 마지막 노드의 링크 필드는 언제나 'NULL' 값임
• 그래서 마지막 노드의 링크 필드를 활용하면서 프로그램 성능에 도움이 되도록 하기 위해서 원형 연결 리스트가 제안이 됨.

---

✅ 2. 원형 연결 리스트

• 연결리스트의 마지막 노드의 링크 필드를 활용해 순환 구조를 이루는 연결 리스트를 의미함.

(1) 원형 연결 리스트의 생성

• 원형 연결 리스트는 단순 연결 리스트와 동일한 코드로 정의되고 생성이 된다.

(2) 원형 연결 리스트의 노드 삽입

• malloc(memory allocation) 의해서 메모리를 할당 받는데 listNode 의 사이즈 만큼 할당을 받는 것이다.
• 그 후, 만들어진 새로운 노드에 data 필드에는 x 데이터와 link 부분에는 NULL 을 넣게 되면 새로운 노드가 만들어진 것이다.

• 기존의 원형 연결 리스트의 새로운 노드가 만들어질 때 경우에 따라서 만들어지는 로직이 조건문을 통해 분기가 됨.
• 즉, 기존의 원형 연결 리스트가 생성이 되어있는 상태이고 리스트 내부가 공백인 경우와 공백이 아닌 경우에 따라 새로 만들어지는 노드가 어떤식으로 처리가 될지 달라짐.
• 또한, 위의 이미지 예시에 마지막 부분 H -> head = NewNode 에 넣으므로 이 예시는 head 에 새로 만들어진 NewNode 를 넣는 경우이므로, 원형 연결 리스트의 제일 첫 번째 부분에 넣겠다는 의미를 가지고 있음.

(3) 원형 연결 리스트의 노드 삽입 - 연결 리스트 공백 여부 조건문 분기

[ 연결 리스트가 공백인 경우 ]

 

• 원형 연결 리스트가 공백인 경우 새로 만든 노드의 주소값을 head 에 넣어주고, 새로 만들어진 노드의 link 에는 자기 자신의 주소값을 참조를 하게 된다. 즉, 원형 연결 리스트의 순환 구조가 만들어짐.

[ 연결 리스트가 공백이 아닌 경우 ]

< 1 >

• 반복문을 통해 연결 리스트의 마지막 노드를 찾게 됨.

< 2 >

• tempNode 가 가리키는 link 즉, 자기 자신의 link 값을 NewNode 새로운 노드의 link 에 넣은 구조이다.

• 이후 tempNode 의 link 부분에 NewNode 를 넣게 되면 새로운 노드의 주소값이 들어가게 된다.
• 즉, tempNode 의 link 에는 NewNode 의 주소값이 들어가게 된다.

< 3 >

• 최종적으로 head 에 NewNode 를 넣어 기존에 참조하고 있던 tempNode 의 주소값을 NewNode 로 덮어 씌우게 됨.
• H -> head = NewNode; 이 부분은 원형 연결 리스트의 제일 첫 번째 위치에 넣기 위한 로직이므로 이렇게 넣게된 경우고 핵심은 공백인 경우와 공백이 아닌 경우에 따라서 분기가 된다는 것만 알면 됨.

(4) 원형 연결 리스트의 노드 삽입 - 특정 노드 뒤에 삽입하는 경우

[ 특정 노드 뒤에 삽입하는 경우 ]

NewNode 삽입 전 초기 상태

NewNode 삽입 후 최종 상태

• 원형 연결 리스트의 중간 위치(prevNode 뒤)에 노드를 삽입하는 연산 예시이다.
• 이미지의 초기 상태 이후 NewNode 가 생성되고 prevNode link 를 NewNode 의 주소값으로 변경
• 그리고 NedNode 는 prevNode 가 가지고 있던 link 값을 NewNode 의 link 로 넣어주게 됨.
• 이렇게 되면 마지막 부분에 새로운 노드를 삽입하는 경우처럼 보일 수 있지만, 결과적으로 특정 노드 뒤에 노드를 삽입하는 것과 동일하게 적용이 될 수 있음.

• 원형 연결 리스트에 새로운 노드를 특정 노드 뒤에 삽입하는 연산이다.

• 먼저 초기에 link 값이 NULL 인 NewNode 즉, 새로운 노드를 만드는 연산을 수행하게 됨. ( 이미지와 같이 만들어짐 )

• 이후, 기존 prevNode 의 link 값을 NewNode link 에 넣어주게 된다.
• 즉, prevNode 가 가리키던 주소값 5000을 NewNode link 에 넣어줌으로써 NewNode 도 같이 가리키는 상황이 됨.

• 이후, NewNode 의 주소값을 prevNode 의 link 에 넣어줌으로써 최종적으로 삽입이 된 원형 연결 리스트의 모습이 됨.

(5) 원형 연결 리스트의 삭제

• 원형 연결 리스트에서 삭제를 할 때에는 특정한 노드를 찾아서 삭제를 해줘야함.
• 아래의 로직은 원형 연결 리스트의 삭제를 하는 코드로 볼 수 있음.

• 먼저 조건문을 통해 해당 원형 연결 리스트가 공백인지(H -> head == NULL) 와 아닌지를 파악을 하게 된다.
• 이유는, 원형 연결 리스트가 공백인 경우에는 애초에 노드가 없기 때문에 삭제가 불가능 하기 때문임.
• 공백이 아닌 경우에는 반복문을 통해 data 와 값이 맞는 노드가 있는지 리스트를 쭉 스캔을 하게 된다.
• 만약 찾았다면 삭제 함수 호출하면서 검색 함수는 끝이 될 수 있음.
• 만약 못 찾았다면 즉, 찾는 값이 존재하지 않을 경우에는 예외처리를 해주게 된다.

(6) 원형 연결 리스트의 삭제 - 과정

• H 는 원형 연결 리스트의 head 의 주소값을 가지고 있으므로, prevNode 에 넣어줌으로써 head 를 가리키게 된다.

•  tempNode = H -> head; 로직은 tempNode 구조체 포인터 변수 생성 후 그 안에 첫 번째 노드(head)의 주소값을 넣은 상황이다. 즉, head 는 리스트의 첫 번째 노드 주소를 가지고 있는 포인터고 tempNode 는 그 주소값을 그대로 복사해서 같은 노드를 가리키게 한 포인터 변수로 볼 수 있음.
• 결과적으로 이미지와 같이 tempNode 는 head 의 주소값을 통해 5000 번 노드로 간 상황이 된다.

• 이후, prevNode = tempNode 즉, prevNode 에 tempNode 를 넣어주게 되면 prevNode 가 기존 tempNode 의 주소값을 참조하게 되면서 prevNode 의 주소값은 5000이 된다.
• tempNode = tempNode -> link; 로직은 tempNode 의 link 에는 다음 노드의 주소값이 들어가 있으므로, 다음 노드를 포인팅 하게 되면서 tempNode 는 주소값 6000 으로 이동을 하게 된다.
• 결과적으로 노드의 link 를 통해 이동하면서 data 비교를 통해 원하는 요소의 위치로 가게 된다. 즉, 순회를 돔
• 이후, deleteCircularNode() 함수를 통해 해당 노드를 삭제 하게 된다.

• deleteCircularNode() 함수에서는 먼저 lastNode 포인터 변수를 만들어 head 가 가리키는 주소값과 lastNode 의 link 값을 비교하면서 반복문을 돌게 되면, lastNode 가 어떤 노드인지 알 수 있게 된다. 즉, lastNode 에는 원형 연결 리스트의 마지막 노드로 이동을 하게 된다. 이후, 이러한 lastNode 를 활용해서 삭제를 진행하게 된다.

• prevNode -> link 즉, prevNode 의 link 는 삭제 할 노드의 주소값을 가지고 있는 상태이므로, 이것을 delNode 변수 즉, 삭제 할 노드로 간주하고 link 값을 넣게 되면 delNode 인 삭제 할 노드가 결정이 되게 된다.

• 이후, delNode 가 가리키는 link 부분을 prevNode 가 가리키는 link 로 바꿔주게 된다.
• 이렇게 되면 prevNode 와 delNode 둘 다 lastNode 의 주소값을 참조하게 된다.
• 이후, 조건문에서 delNode == H -> head 인 경우는 삭제 될 노드가 head 가 가리키는 노드의 주소값이 동일 한 경우 lastNode 의 link 값을 head 가 참조하는 주소값으로 넣게 된다.

• 최종적으로 delNode 를 삭제하게 된다. 이러면 원형 연결 리스트는 유지가 된 상태로 삭제가 된다.

---

✅ 3. 이중 연결 리스트

(1) 단순 연결 리스트의 단점

• 어떤 노드를 찾았을 경우, 그 특정 노드의 후행 노드는 쉽게 찾을 수 있었지만, 어떤 특정노드의 선행 노드를 찾으려면 복잡한 방법이 필요함
• 쉽게말해, 어떤 특정 노드의 선행 노드를 찾는 과정이 매우 까다롭고 힘들다는 단점이 있음.

• 단순 연결 리스트의 단점을 보완하고자 이러한 구조를 가진 이중 연결 리스트가 등장함.

(2) 이중 연결 리스트 - 노드 구조

• 양쪽 방향으로 순회할 수 있도록 head 링크 필드가 왼쪽 시작점(Lhead) 오른쪽 시작점(Fhead)두 개 필요함
• 두 개의 링크 필드 Llink, Rlink 와 한 개의 데이터 필드 구조를 가짐.

(3) 이중 연결 리스트 - 정의 및 생성

• 위와 같이 헤드 노드와 일반 연결 리스트의 노드의 구조체를 정의 할 수 있음.

• 이후, 생성 과정에서는 노드가 아무것도 없는 상태이므로, 기존과 동일하게 NULL 을 넣어 초기화를 할 수 있음.

(3) 이중 연결 리스트 - 특정 노드 삽입

• 새로운 노드를 만드는 로직으로, link 부분 초기값에는 NULL 이 들어가게 됨. ( 새로운 노드 정의 )

• 이러한 초기 상태를 가지는 이중 연결 리스트가 있다고 가정하겠음.

• 새로운 노드를 정의한 뒤 넣는 과정은 위와 같은 코드의 과정으로 이루어질 수 있음.

• 넣을 위치를 prevNode 뒤로 보며, 해당 위치에 넣기 전에 NewNode 의 Rlink 가 prevNode 뒤의 노드의 주소값을 가지게됨.

• 이후, prevNode 의 Rlink 부분에 NewNode 를 넣게 되면, NewNode 의 주소값을 가지는 형태가 됨.

• 이후, NewNode Llink 부분에 prevNode 의 주소값을 넣게 되면 왼쪽 연결이 되게 된다.

• 최종적으로 NewNode 의 Rlink 부분을 보면 4000 번대의 주소로 오른쪽 노드의 주소를 가지고 있음.
• 이 주소를 통해 Llink 로 접근이 가능한데, 접근을 한 뒤 NewNode 의 주소를 넣게 되면 NewNode 오른쪽의 노드 주소가 NewNode 의 주소를 가리키게 됨.

• 결과적으로 최종 상태는 위와 같은 형태로 만들어지게 된다.
• 이중 연결 리스트의 노드 삽입 과정은 내부적으로 위와 같은 형태의 알고리즘을 통해 들어갈 수 있다고 보면 됨.

(4) 이중 연결 리스트 - 특정 노드 삭제

• 해당 로직을 통해 이중 연결 리스트의 특정 노드를 삭제 할 수 있다.

• 이중 연결 리스트의 삭제 초기 상태에는 이미지와 같이 delNode 의 위치를 아는 상태이다.
• 이유는, 삭제를 할 때 어떤걸 삭제 할 지 알려줘야 하는데, 그때 delNode 의 주소값을 주고 삭제하기 때문임.

• 이후, delNode -> Link -> Rlink = delNode 의 Llink 의 Rlink 를 의미하며 그 곳에 delNode 의 Rlink 를 넣게 된다.
• 그러면 delNode 의 Rlink 값이 선행노드의 Rlink 에 들어가게 된다.

• 이후, delNode 의 Rlink 의 Llink 즉, 후행노드의 Llink 값에 delNode 노드의 Llink 값을 넣어주게 된다.
• 그러면 delNode 의 선행, 후행 노드간의 연결이 이뤄지게 된다.

• 이후, delNode 를 삭제하게 되면 기존 delNode 의 선행 후행 노드간의 연결이 되어있으므로 연결된 형태가 됨.