자료구조(2) 연결리스트 + 더미, 머리추가, 정렬기준 함수 정의

필요할 때마다 바구니의 역할을 하는 구조체 변수를 하나씩 동적 할당해서 이들을 연결한다

(메모리 공간을 마련하는 유일한 방법은 malloc 또는 그와 유사한 성격의 함수)

 

참고로 자료구조는 코드를 통해서 공부하는 과목이 아니라, 코드를 통한 학습 이전에, 그림으로 설명하고 이해해야 하는 과목이다.

 

ADT의 정의는 어렵지 않으니 별 것 아니라고 생각할 수 있다. 하지만 신경쓰지 않으면 자료구조에 대한 잘못된 이해를 갖게될수도있다. 따라서 가급적 다음 세가지 순서는 계속 상기시켜야한다

• 자료구조의 ADT 정의
• 정의한 ADT의 구현
• 구현이 완료된 자료구조의 활용

위의 과정을 모두 밞지않으면, 특히 ADT의 정의를 생략하면 구현도 활용도 이상한 형태로 흘러가기 쉽다.

 

head가 가리키는 노드를 그냥 삭제해 버리면, 그 다음 노드에 접근이 불가능하다

 

기능적으로 무인가 변경하거나 추가하지 않는다면 ADT를 변경할 이유는 없다. 그래서 앞서 정의한 배열리스트 ADT를 그대로 가져와 연결리스트(포인터)에 적용해도 된다.+단 정렬 관련기능만 추가

 

ADT에는 명시되어 있지는 않지만 다음내용과 관련해서 결정을 해야한다

• 새 노드를 추가할 때, 리스트의 머리와 꼬리 중 어디에 저장을 할 것인가?

 

머리에 추가할경우 장단점

장점 : 포인터 변수 tail이 불필요하다

단점 : 저장된 순서를 유지하지 않는다(역순으로 출력됨)

 

꼬리에 추가할경우 장단점

장점 : 저장된 순서가 유지된다.(정순으로 출력됨)

단점 : 포인터 변수 tail이 필요하다

 

결론 : 어떠한 방법이 더 좋다고 판단할 성격의 문제는 아니다. 다만 학습과정에서는 "포인터 변수 tail을 유지하기 위해서 넣어야 할 부가적인 코드가 번거롭게 느껴질 수 있다. 게다가 리스트 자료구조는 저정된 순서를 유지해야 하는 자료구조가 아니다!"

 

리스트의 정렬ADT : 정렬의 기준이란 것이 정수를 대상으로 보면 수의 크기가 전부지만, 경우에 따라서는 알파벳의 순서나 이름과 같은 문자열 길이의 길고 짧음이 대상이 될 수도 있다. 따라서 다양한 가능성을 염두해두고 ADT를 정의해야 실제 쓸모 있는 자료구조를 만들 수 있다.

 

더미 노드가 없을 경우 "노드를 추가, 삭제, 그리고 조회하는 방법에 있어서 첫 번째 노드와 두 번째 노드에 차이가 있다" 더미노드를 삽입할 경우 모든 과정을 일관된 형태로 구성할 수 있다.

좋은조합 = (더미노드 + 머리추가) // 일련된 형태로 구성하면서 tail이 불필요해진다.

 

• Node * head;
• Node * cur;

위 유형의 포인터 변수들은 main 함수 내에도 전역변수로도 선언해서는 절대 안된다. 왜냐하면 필요에 따라서 다수의 리스트 자료구조가 필요하기 때문이다.(안그러면 중복해서 위의 포인터들을 중복해서 선언해야함)

 

노드의 추가는 리스트의 멤버 comp에(정렬기준) 무엇이 저장되어 있느냐에 따라서 FInsert 또는 Sinsert 함수를 통해서 진행이 된다. 그런데 이 두 함수 모두 헤더 파일에는 선언된 함수가 아니다. 즉 리스트를 사용하는 프로그래머는 이 두 함수를 직접 호출할 수 없다. 리스트 내부적으로 호출이 되도록 정의된 함수들이기 때문이다.

+설명) main 함수에 리스트 헤더를 포함하고 그 헤더안에 FInsert 또는 Sinsert 함수가 정의되지 않더라도 LInsert는 정의되어있고, Linsert함수를 사용하면 컴파일러는 LInsert함수코드를 구현한 소스코드 페이지로 이동하게되는데 그 페이지안에 Finsert, Sinsert 함수가 정의되어있기 때문에 결과적으로 프로그래머는 FInsert 또는 Sinsert 함수에 직접 접근할 수는 없지만 LInsert를 통해서, 즉 리스트 내부적으로  FInsert 또는 Sinsert 함수를 호출할 수 있게되는것이다.

 

about LRemove

Lfirst 또는 Lnext 함수가 호출되면 before는 다시 cur보다 하나 앞선 노드를 가리키게 되므로 굳이 before의 위치까지 재조정할 필요는 없다. 무엇보다도 노드들이 한쪽 방향으로만 연결되어 있기 때문에 before를 한 칸 왼쪽으로 이동시키기 위해서는 그만큼 대가를 치러야 한다.(굳이 하자면 가능할꺼같은데 많은 연산이필요함)

 

정렬기준 설정 관련된 부분

• 연결리스트의 정렬기준이 는 함수를 등록하는 SetSortRule 함수
• SetSortRule 함수를 통해서 전달된 함수정보를 저장하기 위한 LinkedList의 멤버 comp
• comp에 등록된 정렬기준을 근거로 데이터를 저장하는 SInsert 함수
• 프로그래머 정의 함수 WhoIsPrecede함수 (main함수가 정의되어 있는 소스파일에 삽입, 밑에 이유)

//함수의 위치는 main! 프로그래머가 연결 리스트의 정렬 기준을 결정하도록 유연성을 부여했기 때문에!