[자료구조] 연결리스트(DLinkedList)

사실 연결리스트는 스킵하려했는데 
앞선 그래프 구현할때 많이 쓰여 정리한다.

 

---

[ DummyNode LinkedList ]

 

일반 리스트 즉 LinkedList를 더 효율적으로 만든게
Dummy노드를 활용한 DLinkedList이다.

DummyNode를 활용하면 LInsert와 LRemove 과정이 편해진다

하지만 LInsert가(데이터 추가할때) 리스트의 맨 끝에 하는게 아닌 앞에 하는거로 바뀐다
이렇게 바뀌는 이유는 DummyNode 때문이다.

하지만 앞에 추가한다고 문제가 되는 건 아니다.

왜냐하면 연결리스트란 자료구조가 스택Stack이나 큐Queue 처럼

데이터들의 저장순서가 중요하진 않기 때문이다.

그저 해당 리스트에 말그대로 저장만 하면 되기 때문에 

앞에 저장하건 뒤에 저장하건 내 알빠 아니다.

만약 DummyNode를 사용하지 않는 일반적인 LinkedList라면
LInsert시에 첫번째 데이터인지 아닌지 나눠서 저장해야한다

왜냐하면 첫번째 데이터일때는
head에 newNode를 저장하고
아닐때는 tail->next에 저장해야하기 때문이다

아래와 같이 말이다
 

newNode = (Node*)malloc(sizeof(node))

if(head==NULL) head->newNode;
else tail->next = newNode;

하지만 DummyNode를 이용하고
새롭게 추가된 데이터를 앞쪽에 저장하는 DLinkedList를 사용하면
위와 같이 구분안하고 코드를 작성할 수 있다

항상 head는 더미노드를 가리키고 있기때문에
head 를 신경써줄 필요가 없기 때문이다.

 

---

[ LinkedList와 Node 구조체 ]

typedef int LData;

typedef struct _node {
	LData data;
	struct _node * next;
}Node;

typedef struct _linkedList {
	Node* head; // Dummy Node를 가리키는 고정포인터
	Node* cur; // LFirst LNext하면서 움직이는 동적포인터
	Node* before; // LFirst LNext 하면서 움직이는 동적포인터(cur바로 전 놈을 가리킴)
    int numOfData;
}LinkedList;

 

 

Node* head :  DummyNode를 가리키는 고정포인터
Node* cur :  LFirst LNext 하면서 움직이는 동적포인터
Node* before : LFirst LNext 하면서 움직이는 동적포인터 ( cur 보조해줌 )

 

---

[ Functions ]

void ListInit(List* plist) {
	// 시작할때 DummyNode 생성
	plist->head = (Node*)malloc(sizeof(Node));
	plist->head->next = NULL;
	plist->numOfData = 0;
}

리스트 초기화 함수이다.

DLinkedList이므로 초기화 시 DummyNode를 생성한다.

 

int LFirst(List* plist, LData* pdata) {
	// DummyNode의 next가 NULL이면 == 아무 데이터가 없으면
	if (plist->head->next == NULL) return 0;
	else {
		// 있으면 첫번째 데이터 읽기
		plist->before = plist->head;
		plist->cur = plist->head->next;
		*pdata = plist->cur->data;
		return 1;
	}
}

"첫 번째 데이터가 pdata가 기리키는 메모리에 저장된다"

 

여기서 LFirst 함수는 오로지 첫번째 데이터만 반환하는 함수이다.

데이터의 유무도 파악해준다.

얘는 DummyNode가 가리키는 노드만 참조한다

 

 

int LNext(List* plist, LData* pdata) {
	if (plist->cur->next == NULL) return 0;
	
	// before cur 포인터 옮겨주기
	plist->before = plist->cur;
	plist->cur = plist->cur->next;

	*pdata = plist->cur->data;
	return 1;
}

"참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다"

 

이 LNext 함수는 LFirst 이후에 호출되어야하는 함수로

LinkedList 구조체의 cur before 포인터를 최신화하며 리스트를 탐색한다

 

 

void LInsert(List* plist, LData pdata) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = pdata;
	newNode->next = plist->head->next;
	// 새 데이터는 앞쪽에 추가
	plist->head->next = newNode;
	plist->numOfData++;
}

 

 

LData Remove(List* plist) {
	Node* rpos = plist->cur;
	LData data = rpos->data;

	// node 관계 재정립
	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	plist->numOfData--;
	return data;
}

 

---

[ main ]

while (LFirst(&list, &data)) {
	printf("%d", data);
	while (LNext(&list, &data)) {
		printf("%d", data);
	}
}

 

데이터 참조 절차가 LFirst와 LNext, 

첫번째 데이터냐 아니냐로 구분되어 있기때문에

위와 같이 구성하여 탐색해야한다.