1. 링크드 리스트의 활용 : 다항식

더블 포인터를 쓰는 대신에 ListHeader 를 사용하면 더 쉽게 구현 가능하다. 이렇게 구조체를 만들고, 그 구조체에 노드의 주소를 저장하는 노드를 만들면, 주소를 저장하는 노드가 되기 때문에, 주소를 저장하는 변수라는 점에서 더블 포인터와 같은 역할을 하게 됨. 즉 심플 링크드 리스트와 circular 링크드 리스트에서 head pointer 를 쓰는 대신 List Header 를 쓸 수 있음.

• ListHeader 의 주소를 저장하는 *plist 를 이용하면, 더블 포인터 사용을 피할 수 있음.
• init 함수는 매개변수로 ListHeader 의 주소를 가져온 다음에 그것의 head 와 tail 에 접근하여 null 을 저장하고, length 에는 0을 넣어주는 함수. 즉 초기화시키는 함수임.
• insert_node_last 함수는 매개변수로 ListHeader 의 주소, 넣고 싶은 값의 상수와 차수를 int 변수로 받아옴. 그 다음에 Lisnode 하나를 메모리 동적 할당을 통해 만들고, 그 곳에 상수와 차수를 넣고, 일단 Link 에는 NULL 을 넣어줌. 그리고 나서 만약, 빈 배ㅕㅇㄹ일 경우, pList 의 헤드와 테일에 모두 넣고 싶은 노드의 주소를 넣어줌. 만약 아닐 경우, plist 의 테일의 링크에 노드의 주소를 넣어주고, tail 의 값을 새로운 노드의 주소로 수정함. 그리고 마지막으로 plist 의 length 값을 1 증가시킴.

• poly_add 함수는 매개변수로 ListHeader 의 주소 3개를 받는다. 그 후 Listnode 의 주소를 저장하는 변수 두 개를 만든다. 그리고 각각의 변수에 head 의 주소를 담는다. 그 다음 while 문을 돌리는데, 조건은 a 와 b 모두 널이 아닐 때까지만이다. 그 뒤의 내용은 앞서 봤던 링크드리스트의 다항식의 합 부분과 유사하다. 먼저 a의 차수가 b의 차수와 같은 경우, 두 노드의 상수의 합을 저장한다. 그 뒤에 insert_node_last 를 이용하여 합이 0이 아닌 경우에만, 결과 리스트에 해당 값을 저장해 준다. 그리고 나서 a와 b에 링크의 주소를 입력한다. 만약 a의 차수가 b의 차수보다 더 큰 경우, 새로운 노드에 insert_node_last 를 해 주고, a의 차수와 상수를 전달해 준다. 그리고 나서 a에는 a의 링크를 저장해 준다. b의 차수가 더 큰 경우 vice versa. 그렇게 반복문이 끝나고 나면, 마지막으로 a와 b의 값이 널이 아닐때까지 도는 반복문을 각각 만들어 준 뒤에 insertnodelast 해 준다.

• print 의 경우, 리스트헤더 plist 를 주소로 받아온 다음에 노드의 주소를 저장하는 변수를 하나 만들고, head 를 저장해 준다. 그리고 그것이 null 이 될 때까지 도는 반복문을 설정해 주면 된다.

2. 링크드 리스트를 사용한 List ADT

• List ADT 를 링크드 리스트를 이용해 구현해 보자.
• 먼저

add 와 delete 의 파라미터는 값을 넣거나 빼고 싶은 위치이다.(주소 아님. 노드의 번호 자체) → position

insert_node 와 remove_node 의 파라미터는 node 의 위치를 알려주는 주소이다. (좀 더 구체적)