[Data Structures][04-1] 연결 리스트의 개념적인 이해

목차
Chapter 04. 연결 리스트(Linked List) 2

Chapter 04-1: 연결 리스트의 개념적인 이해

- Linked! 무엇을 연결하겠다는 뜻인가!

- 예제 LinkedRead.c의 분석

  - 초기화

  - 삽입 1회전

  - 삽입 2회전

  - 데이터 조회

  - 데이터 삭제

---

연결 리스트의 개념적인 이해

 배열을 동적 할당하는 방법을 배우는 것이 아닌, 배열을 연결 후 배열을 대체할 수 있는 하나의 자료구조를 만드는 것이 연결 리스트이다.

 

Linked! 무엇을 연결하겠다는 뜻인가!

 

구조체 node

1. Data를 담을 수 있어야 한다.

2. 연결을 할 수 있어야 한다.

 

 

 위 그림을 보면 이전 data가 다음 data를 포인터로 가리키고 있다. 이런 식으로 가리키면 쭉 노드들이 연결된다. 이것을 연결 리스트라고 한다.

 

예제 LinkedRead.c의 분석

초기화

 

 

head, tail, cur 세 가지 요소가 연결 리스트의 핵심이다.

(연결 리스트에서 head는 필수적이지만 tail은 없을 수도 있다)

 

head -> 연결 리스트의 머리를 가리키기 위한 포인터 변수

tail -> 연결 리스트의 꼬리를 가리키기 위한 포인터 변수

cur -> 저장된 데이터 조회에 필수적인 포인터 변수

 

각각의 포인터 변수를 NULL로 초기화합니다.

 

삽입 1회전

 

 

노드 추가과정을 보면 노드를 newNode로 동적 할당해주고 readData, Null로 각각 초기화해줍니다.

 

그리고 if문을 보면 head가 NULL이기 때문에 head가 newNode를 가리키게 합니다. (조건문, 분기가 적을수록 더 좋은 모델임) 

 

마지막으로는 tail도 해당 노드를 가리키도록 합니다.

 

삽입 2회전

 

 

 1회전 이후에는 head는 그대로 있고 tail부분은 새롭게 들어오는 노드를 가리키게 됩니다. (else문)

 

 그렇기 때문에 다수의 노드를 저장한 결과는 다음과 같이 쭉 이어지는 모습을 보입니다.

 

데이터 조회

 

 

 조희를 할 때 순차적으로 접근한다. if(head == NULL)로 예외 처리를 해주고, cur 포인터를 사용해 head를 가리키게 합니다. 이후 while문을 돌게 되는데, while문 조건으로는 NULL이 아닌 경우에 돌게 하여, current 포인터가 가리키고 있는 멤버 next를 불러와, 다음 데이터를 계속 참조하게 하여 모든 데이터를 조회할 수 있게 합니다.

 

데이터 삭제

 

 

 삭제 과정을 진행하려면 Node 포인터 변수가 2개 이상 필요하다. 

 

 head가 가지고 있는 값을 delNode로 가리키게 합니다. delNextNode로는 head 다음 노드를 가리키게 합니다. (head->next) 그리고 현재 가리키고 있는 delNode를 free로 삭제합니다. 

 

 두 번째 노드부터는 지우고 남은 현재 가리키고 있는 노드를 delNode로 옮기고(delNode = delNextNode) delNextNode가 가리키고 있는 멤버 next를 다시 delNextNode로 가리키게 합니다.(delNextNode->next)

 

 마지막으로 delNode를 동적 할당 해제해줍니다.(삭제)

 

 이런식으로 하지 않고 delNode를 바로 지울 수 없는 이유는, delNode, Node 포인터 변수 안의 멤버로 next가 있기 때문입니다. 바로 지우게 되면, next, 옆에 있는 것을 참조할 수 없어서 다음 값으로 이동할 수 없습니다. 그렇기 때문에 delNextNode를 만들어주고 delNode의 next값을 참조하게 합니다. (delNextNode = delNextNode->next를 보면 계속 옆으로 이동하게끔 할당해줌)

 

 위처럼 구분 되게 모델을 구현하는 것은 좋은 모델은 아닙니다.

 

---