단순 연결 리스트
연결 리스트는 각 데이터들을 포인터로 연결하여 관리하는 구조입니다.
연결 리스트에는 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 등이 있습니다.
우선 단순 연결리스트에 대해서 배워보도록 하겠습니다.
말 그대로 단순하게 한 방향으로 전개되고 끝이 존재합니다.
구현을 할 때 더미노드가 있으면 굉장히 편리합니다 .
왜냐하면 더미노드가 있을 경우 더미노드 이후 데이터가 들어가기 때문에 일관 된 형태로 추가, 삭제 ,조회등을 할 수 있습니다.
1)더미노드 생성과 초기화
즉 위의 사진처럼 헤드가 더미노드를 가리키게 하면 됩니다.
우선 단순 연결 리스트를 표현하는데 있어서 필요한 도구들을 살펴보겠습니다.
노드의 구조체를 표현해야합니다.
즉 Node라는 구조체로 리스트를 표현합니다.
head는 더미노드를 표현하기위해서, cur은 현재로 참조또는 삭제를 돕습니다.
before는 삭제를 돕습니다.
numOfData는 데이터 수를 표현합니다.
(*comp)(LData d1,LData d2)는 정렬의 기준 등록 함수입니다.
위의 두 구조체를 통해 필요한 도구는 끝났습니다.
이를 잘 활용하면 되겠습니다.
이는 리스트를 표현하기 위한 함수들입니다.
typedef로 LinkedList 구조체를 List로 간단히 표기했습니다.
ListInit함수는 리스트초기화를 담당합니다.
즉 위의 LinkedList 구조체를 초기화하는 단계입니다.
즉 List의 맴버 head를 동적 할당 해줍니다.(더미노드 생성)
head의 next를 null로 초기화 시켜주고 비교함수도 null 개수도 0으로 초기화시켜줍니다.
2) 삽입& 조회
이제 삽입을 하는 함수를 살펴보도록 하겠습니다.
LInsert함수는 삽입함수로 리스트와 데이터를 인자로 전달 받습니다.
comp함수가 없다면(정렬 x)
FInsert 함수를 통해 머리에 삽입시킵니다.
정렬 기준이 됐다면 그것에 근거해서 SInsert함수를 통해 삽입시킵니다.
FInsert함수를 보도록 하죠
우선 삽입할 새 노드를 newNode로 생성합니다.
1.데이터를 넣고 새로운 노드의 next를 원래 더미노드가 가리키던 next에 연결 시킵니다. 뒤 연결(newNode->next=plist->head->next)
2. 더미노드가 새 노드를 가리킵니다. 앞 연결(plist->head->next=newNode)
이것이 바로 FInsert함수 구현입니다.
삽입을 했다면 이제 데이터를 검색하고 참조를 해야겠죠
참조에 대해서 살펴봅시다.
우선 참조는 before맴버를 더미노드를 가리키게 하고 cur은 첫 노드를 가리키게 합니다.
1.before맴버를 더미노드(head)를 가리키고
2.cur맴버를 더미노드 다음(next)를 가리킵니다.
그다음 pdata에 cur이 가리키는 데이터를 담습니다.
그다음 LNext 함수로 다음 데이터를 조회합니다.
LNext함수는
cur이 가리키던 것을 before가 가리키게 합니다.(plist->before=plist->cur)
그리고 cur은 다음 노드를 가리키게 합니다.(plist->cur=plist->cur->next)
3) 삭제
삭제에 대해서 알아보죠
그림으로 보시죠.
삭제 전에는 before와 cur이 이 상태입니다.
삭제 후에는 cur이 가리키던 노드를 없애고 before가 가리키는 것이 cur이 가리키던 다음 노드를 가리키면서
cur은 앞의 노드를 가리키게합니다.
우선 rpos에 현재 cur을 담습니다.
rdata에는 rpos의 데이터를 담습니다.(cur의 데이터)
이 코드는 노드를 없애고 연결 시키는 방법입니다.
before의 다음이 cur이 가리키던 next를 가리킵니다.
cur은 before를 가리킵니다. 위 삭제 후 사진이 되겠죠
동적 해제를 하고 개수를 감소시키고 삭제 데이터를 반환합니다.
즉 이를 전체 코드로 보면
SInsert함수는 정렬 기준으로 삽입하는 것으로 comp함수로 들어갈 자리를 못찾고 더미노드가 마지막이아니라면 계속 탐색해서 삽입합니다.
