5. Doubly Linked List

Doubly Linked List

Doubly Linked LIst 가 일반 Linked List와 다른 것은 각 노드가 next 뿐만 아니라, front 노드 값도 저장하고 있다는 점이다. 따라서 리스트에서 앞 뒤 데이터를 추출하기에 용이하다.

 

또 하나 다른 점은 LIST 안에 rear 포인터를 두어서 리스트의 마지막 노드도 참조할 수 있도록 했다. 비록 이건 반드시 Doubly Linked List의 특징이라고 할 수 없겠지만, 연습을 위해 추가해보았다.

 

data.h & data.c

매우 간단하다. 심지어 따로 compare 함수를 사용하지도 않았고, key가 int형이라고 고정한 상태로 compare 하는 과정도 dll.c 안에 코드를 짜버렸다.

typedef struct myData {
	int key;
	int field;
}MYDATA;

MYDATA* createData(int k, int f);

#include <stdio.h>
#include "data.h"

MYDATA* createData(int k, int fi) {
	MYDATA* myData = (MYDATA*)malloc(sizeof(MYDATA));
	myData->key = k;
	myData->field = fi;
	printf("data created; [k: %d, f: %d] \n", myData->key, myData->field);
	return myData;
}

int compareKey(MYDATA* arg1, int key) {
	int result = arg1->key - key;
	return result;
}

dll.h

#include <stdio.h>
#include "data.h"

typedef struct node {
	struct NODE* next;
	struct NODE* front;
	MYDATA* dataptr;
}NODE;

typedef struct myList {
	NODE* head;
	NODE* rear;
	int count;
}LIST;

LIST* createList();
void addNode(LIST* myList, MYDATA* data);
int traverse_print(LIST* myList);
int reverse_print(LIST* myList);
NODE* retrieveNode(LIST* myList, int key);
void destroyList(LIST* myList);
void removeList(LIST* myList, int k);

int _searchList(LIST* myList, NODE** ppPre, NODE** ppLoc, int key);

reverse_print 는 LIST 구조체 안에 rear가 잘 들어갔는지, 각 NODE 안에 front가 잘 세팅되어있는지 확인하기 위해 리스트의 rear부터 front를 참조하여 프린트해본 함수이다.

기존과 다른 점이 있다면, _insert, _delete 등 private한 함수를 거의 만들지 않고 _searchList정도만 사용했다. _searchList는 addNode, retrieveNode, removeNode 등에서 key와 일치하는 노드를 찾는 역할이다.

 

dll.c

#include "dll.h"

LIST* createList() {
	LIST* myList = (LIST*)malloc(sizeof(LIST));
	if (myList != NULL) {
		myList->head = NULL;
		myList->rear = NULL;
		myList->count = 0;
		printf("list created! \n");
	}
	return myList;
}

void addNode(LIST* myList, MYDATA* data) {
	/* This alg inserts data into a doubly linked list.
	 * Pre: list is metadata structure to a valid list data contains the data to be inserted
	 * Post: The data have been inserted in sequence
	 * Return 0: failed -- dynamic memory overflow
	 *        1: successful
	 *        2: failed = duplicate key presented
	 */

	//locate insertion point in list
	NODE* pPre = NULL;
	NODE* pLoc = NULL;
	int found = _searchList(myList, &pPre, &pLoc, data->key);

	if (!found) {
		NODE* newNode = (NODE*)malloc(sizeof(NODE));
		if (newNode != NULL) {
			newNode->dataptr = data;
			if (pPre == NULL) {
				// inserting before first node or into empty list
				if (myList->head != NULL) { 
					// the list is not empty
					myList->head->front = newNode;
				}
				else {
					// the list was empty
					myList->rear = newNode;
				}
				newNode->front = NULL;
				newNode->next = myList->head;
				myList->head = newNode;
			}
			else {
				// inserting into middle or end of list
				newNode->front = pPre;
				newNode->next = pLoc;
				pPre->next = newNode;
				if (pLoc != NULL) {
					// not the rear node
					pLoc->front = newNode;
				}
				else {
					// new Node becomes the rear node
					myList->rear = newNode;
				}
			}
			myList->count++;
			printf("node successfully inserted! \n");
			return 1;
		}
		else {
			// Dynamic Memory overflow.
			return 0;
		}
	}
	//Duplicate data. key already exists.
	printf("key already exists, unable to insert data \n");
	return 2;
}


int traverse_print(LIST* myList) {
	NODE* temp = myList->head;
	printf(">>>>>>>>>>>>>> SHOW LIST <<<<<<<<<<<<<<< \n");
	while (temp != NULL) {
		printf("data: [key] %d   [field] %d \n", temp->dataptr->key, temp->dataptr->field);
		temp = temp->next;
	}
}

/* reverse_print exists to check if LIST::rear and NODE::front are correctly saved */
int reverse_print(LIST* myList) {
	NODE* temp = myList->rear;
	printf(">>>>>>>>>>>>>> SHOW LIST (REVERSED) <<<<<<<<<<<<<<< \n");
	while (temp != NULL) {
		printf("data: [key] %d   [field] %d \n", temp->dataptr->key, temp->dataptr->field);
		temp = temp->front;
	}
}

NODE* retrieveNode(LIST* myList, int key) {
	
	NODE* pPre = NULL;
	NODE* pLoc = NULL;
	if (_searchList(myList, &pPre, &pLoc, key)) {
		// found
		return pLoc;
	}
	else {
		printf("unable to find a node with the key \n");
		return;
	}
}

void destroyList(LIST* myList) {

	printf("count: %d \n", myList->count);
	NODE* pLoc = myList->head;
	NODE* temp = NULL;
	
	while (pLoc != NULL) {
		temp = pLoc;
		pLoc = pLoc->next;
		free(temp->dataptr);
		free(temp);
	}
	free(myList);
	printf("list successfully destroyed! \n");
	
}

void removeList(LIST* myList, int k) {

	NODE* pPre = NULL;
	NODE* pDel = NULL;
	NODE* temp = NULL;

	if (_searchList(myList, &pPre, &pDel, k)) {
		// found the right position
		if (pPre == NULL) {
			// the node being deleted is head node
			myList->head = pDel->next;
			myList->head->front = NULL;
		}else if (pDel->next == NULL) {
			// the node being deleted is rear node
			myList->rear = pDel->front;
			myList->rear->next = NULL;
		}
		else {
			// node is somewhere between nodes
			pPre->next = pDel->next;
			temp = pDel->next;
			temp->front = pPre;
		}
		free(pDel->dataptr);
		free(pDel);
        myList->count--; //수정
		printf("node successfully removed! \n");
	}
	else {
		// unable to find a node with the key
		printf("node not found, unable to remove node \n");
	}
}

int _searchList(LIST* myList, NODE** ppPre,  NODE** ppLoc, int key) {
	/* Searches list and passes back adr of node containing target and its logical predecessor.
	 * Pre: list is metadata structure to a valid list
	    pPre is pointer variable for predecessor
		pLoc is pointer variablefor current node
	* Post: pLoc points to first nodewith equal/grater key
	*		- or - null if target >key of last node
	*       pPre points to largest node smaller than key
	*		- or - null if target < key of first node
	* Return true if found, false if not found */
	int found;
	*ppPre = NULL;
	*ppLoc = myList->head;
	while (*ppLoc != NULL && key > (*ppLoc)->dataptr->key) {
		*ppPre = *ppLoc;
		*ppLoc = (*ppLoc)->next;
	}
	if (*ppLoc == NULL) {
		found = 0; // new node must exist after pPre
	}
	else {
		if (key == (*ppLoc)->dataptr->key)
			found = 1; //key already exists
		else
			found = 0;
	}
	return found;
}

main.c

#include <stdio.h>
#include "dll.h"

int main(void) {

	LIST* myList = createList();

	printf("\n>>>>>>>>>>>>>>>>> DATA INSERTION <<<<<<<<<<<<<<<<< \n");
	MYDATA* myData = createData(4, 7);
	addNode(myList, myData);

	printf("\n");
	myData = createData(2, 9);
	addNode(myList, myData);
	
	printf("\n");
	myData = createData(3, 19);
	addNode(myList, myData);

	printf("\n");
	myData = createData(3, 29);
	addNode(myList, myData);
	printf("\n");
	

	traverse_print(myList);
	printf("\n");

	reverse_print(myList);
	printf("\n");
	
	printf(">>>>>>>>>>>>>>>> TRY NODE RETRIEVAL <<<<<<<<<<<<<<<<< \n");
	NODE* r_node = retrieveNode(myList, 2);
	printf("retrieved data: [k: %d, f: %d]\n", r_node->dataptr->key, r_node->dataptr->field);
	printf("\n");
	
	printf(">>>>>>>>>>>>>>>> TRY NODE REMOVAL <<<<<<<<<<<<<<<<< \n");
	removeList(myList, 2);
	printf("\n");
	traverse_print(myList);

	destroyList(myList);
	
	return 0;
}

결과

 

보니까 removeList()에 count 수를 줄여주는 것을 까먹어서 코드에 추가했으며, 결과 창 마지막 쯤에 있는 count: 3은 오타로 보면 될 것 같다.

 

Circularly Linked List

 

General Linked List 와 Doubly Linked List 등을 모두 구현했으니, Circularly Linked List도 충분히 구현할 수 있다. 그러므로 여기서는 특성만 짚고 넘어간다.

 

- last node's link(next) points to the first node of the list

마지막 노드의 link가 리스트의 첫번째 노드를 가리킨다.

- used in lists that allow access to nodes in the middle of the list without starting at the beginning

처음에서 시작하지 않고 중간에서 바로 노드에 접근할 수 있는 리스트에 사용된다

- when inserting or deleting the last node, in addition to updating the rear pointer in the header, we must also point the link field to the first node

마지막 노드를 추가하거나 삭제할 때, 헤더의 rear 포인터를 업데이트하는 것과 더불어, 반드시 rear노드의 link가 첫 번째 노드를 가리키도록 한다.

 

(특성 출처: Data Structures - A Pseudocode Approach with C,Richard F.Gilberg & Behrouz A.Forouzan)

대표사진 삭제

사진 설명을 입력하세요.