연결리스트 – 원형 연결리스트
원형리스트의 정의 및 특징
- 우리가 구현한 연결리스트의 (단순연결리스트) 마지막 노드 -> NULL 가르킴
그러면 그 마지막 노드가 첫번째 노드를 가리키게 하면 -> 원형 연결리스트!!
- 즉 마지막 노드가 첫번째 노드를 가르켜서 연결의 형태가 원을 이루는 형태
- 원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고 얘기 가능
왜? 결국 두가지 경우 모두 8이 가리키는 건 1이다.
- 장점 : 머리,꼬리를 가리키는 포인터 변수를 각각두지 않아도 하나의 포인터 변수만 있어도 머리 , 꼬리에 노드를 간단히 추가 가능
변형된 원형 연결리스트
- 하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 한다면
새로운 노드가 추가 되었을 때 쉽게 추가가능
- 꼬리를 가리키는 포인터 변수? Tail
머리를 가리키는 포인터 변수? Tail -> next
변형된 연결리스트 구현
- 헤더파일
LFirst, LNext, LRemove 는 활용가치가 높은 함수들
이 중에서 LNext 함수 : 무한 반복 호출 가능, 리스트의 끝에 도달할 경우-> 첫번째 노드부터 다시 조회 시작
- 리스트의 초기화 및 노드의 삽입
리스트의 멤버들을 모두 0, NULL로 초기화시키기
void ListInit(List *plist)
{ plist->tail=NULL;
plist->cur=NULL;
plist->before=NULL;
plist->NumofData=0;}
첫번째 노드의 추가
1. Tail은 새노드를 가리켜야한다.
2. 새 노드도 자기자신을 가리켜야 한다
왜? 처음 추가 된 노드 = 머리이자 꼬리
3. 두번째 이후의 노드 추가
NewNode->next=plist->tail->next;
Plist->tail->next=newNode;
새 노드와 두번째 노드 연결
제일 먼저 추가된 노드와 새 노드 연결
-> 먼저 추가된 노드와 새롭게 추가된 노드를 연결
- LNext 함수
LFirst 함수와 다른점
cur, before을 한칸씩 이동
- 노드 삭제
1. 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 한다.
-삭제할 노드가 tail 가르킴 : tail의 이전 노드가 tail이 된다.
2. cur을 한칸 뒤로 이동
- 삭제할 노드가 리스트에 혼자 남는 경우 : NULL을 삭제
'자료구조' 카테고리의 다른 글
[자료구조]04. 연결리스트 - 연결리스트의 응용 (다항식) (0) | 2021.01.26 |
---|---|
[자료구조]04.연결리스트 (2)- 단순 연결 (0) | 2021.01.25 |
[자료구조]03. 연결 리스트-자료구조 (0) | 2021.01.20 |
[자료구조]01. 알고리즘의 성능분석 방법 - 시간복잡도 / 공간복잡도 (2) | 2021.01.13 |