본문 바로가기
Data Structure

C LinkedList 만들기 (version 2 - Doubly LinkedList)

by SuldenLion 2023. 3. 30.
반응형

C로 LinkedList 구현하기

 

Doubly LinkedList를 C로 구현해 보겠다.

Doubly LinkedList는 Singly LinkedList의 단점을 보완해 만든 LinkedList로, Library에 있는 LinkedList는 Doubly LinkedList로써 구현되어 있다.

Singly LinkedList의 단점으로는 크게 두가지가 있는데, add로 데이터를 추가할때, 맨 끝 노드에 값을 추가하기 위해 매번 traverse를 해줘야 한다는 점과 LinkedList를 traverse 하고자 할 때 정방향으로밖에 못한다는 점이 있다.(역순 traverse 불가)

 

Doubly LinkedList나 Singly LinkedList나 전체적인 로직은 비슷하지만 몇가지 차이점이 있으니 한번 살펴보겠다.

 

리스트에서 쓰일 노드의 차이부터 보겠다.

Singly LinkedList는 멤버 변수로 data와 다음 노드를 가리킬 *next를 가진다. 반면 Doubly LinkedList는 다음 노드뿐만 아니라 이전 노드도 가리키기 위하여 노드를 가리킬 포인터변수 *prev를 가진다. 

각 리스트의 노드에 데이터 x를 넣고 초기화하는 것을 보면 다음과 같다.

 

노드가 초기화 될 때, Singly LinkedList는 데이터에 값을 넣고 다음 노드를 가리킬 포인터에 NULL을 넣어줬지만, Doubly LinkedList에서는 우선 prev*와 next*가 자기 자신 노드를 가리키도록 한다. 이후에 리스트에 노드 insert시 *prev와 *next를 각각 들어갈 위치의 앞 노드와 뒷 노드를 가리키게 하면서 연결시켜주는 것이다.

 

바로 List를 만들어 10, 20 ,30의 숫자를 add() 해보겠다.

add(10)
add(20)
add(30)

add() 작업은 이런식으로 header가 가리키는 노드와 맨 끝에 추가되는 노드끼리도 연결시켜주며 연결된 모든 선이 마치 원모양처럼 표현된다.

 

그렇다면 addFirst는 어떤식으로 되는지 위의 그림에 이어서 addFirst(100)을 해보겠다.

addFirst(100)

즉, 처음 노드와 마지막 노드사이에 노드를 추가해주고 헤더의 참조를 해당 값으로 바꿔주기만 하면 된다.

 

이러한 데이터 추가에 대한 메서드들 외에는 Singly LinkedList와 Doubly LinkedList의 메서드들은 별 차이 없다. 또한 traverse를 역순으로 하고 싶다면 이전 노드를 가리키는 포인터 *prev가 있으므로 prev를 따라가며 해주면 된다.

 

아래 링크는 C로 짠 Singly LinkedList에 대한 글이다.

https://suldenlion.tistory.com/88

 

(C로 자료구조 구현하기) LinkedList 만들기 (version 1)

C로 LinkedList를 직접 구현해 보도록 하겠다. LinkedList는 배열 자료구조의 size 고정 문제를 해결하고, 데이터 삽입/삭제의 문제도 해결되었다는 특징이 있다. LinkedList의 대표 메서드로는 add()와 remove

suldenlion.tistory.com

 

 

 

메인 소스 코드와 LinkedList 구현 코드를 보면서 마무리 하겠다.

#include <stdio.h>
#include <malloc.h>
#include "LinkedList.h"

//doubly LinkedLIst -> Singly LinkedList 단점 보완(add, traverse 역순)

main()
{
	LinkedList list1;
	LinkedList list2;
	LinkedList *list3;
	int *arr;
	int i;

	initList(&list1);
	initList(&list2);

	printf("list1 = ");
	print(&list1);
	printf("list2 = ");
	print(&list2);

	add(&list1, 10);
	add(&list1, 20);
	add(&list1, 30);
	add(&list1, 40);

	add(&list2, 100);
	add(&list2, 200);

	printf("list1 = ");
	print(&list1);
	printf("list2 = ");
	print(&list2);

	//addAt(&list1, 0, 7);
	//print(&list1);

	addAllAt(&list1, &list2, 5);
	printf("list1 = ");
	print(&list1);

	//clear(&list1);
	//print(&list1);

	list3 = clone(&list1);
	printf("list3 = ");
	print(list3);

	//printf("%d\n", contains(&list1,110));
	//printf("%d\n", get(&list1,7));
	//printf("%d\n", getFirst(&list1));
	//printf("%d\n", getLast(&list1));
	//printf("%d\n", indexOf(&list1, 50));
	//printf("%d\n", lastIndexOf(&list1, 7));

	set(&list1, 2, 77);
	printf("list1 = ");
	print(&list1);

	removeData(&list1, 77);
	printf("list1 = ");
	print(&list1);
	
	removeAt(&list1, 1); 
	printf("list1 = ");
	print(&list1);

	arr = toArray(&list1);
	printf("[ ");
	for (i = 0; i < size(&list1); i++) {
		printf("%d ", arr[i]);
	}
	printf("]\n");

	disposeList(&list1);
	/*
	add(&list2, 100);
	add(&list2, 200);
	add(&list2, 300);

	printf("get 0 %d\n", get(&list1, 0));
	printf("getFirst %d\n", getFirst(&list1));
	printf("getLast %d\n", getLast(&list1));
	printf("list1 = ");
	print(&list1);

	printf("list2 = ");
	print(&list2);

	//printf("%d\n", get(&list1, 0));
	//printf("%d\n", element(&list1));
	//printf("%d\n", getFirst(&list1));
	//printf("%d\n", getLast(&list1));
	printf("%d\n", lastIndexOf(&list1, 30));
	
	set(&list1, 3, 700);

	//removeAt(&list1, 2);
	//removeAt(&list1, 0);
	removeData(&list1, 700);
	
	printf("list1 = ");
	print(&list1);

	arr = toArray(&list1);
	for (i = 0; i < size(&list1); i++) {
		printf("%d ", arr[i]);
	}*/
}

 

<LinkedList 헤더 파일>

#ifndef _LINKEDLIST_
#define _LINKEDLIST_

#include <stdio.h>
#include <malloc.h>

#define TRUE	(1)
#define FALSE	(0)

typedef struct _node {
	struct _node *prev;
	int data;
	struct _node *next;
} Node;

typedef struct _linkedList {
	Node *header;
	int count;
} LinkedList;

extern void initList(LinkedList *l);
extern void disposeList(LinkedList *l);
extern void addFirst(LinkedList *l, int x);
extern void add(LinkedList *l, int x);
extern void addLast(LinkedList *l, int x);
extern void addAt(LinkedList *l, int index, int x);
extern void addAllAt(LinkedList *l1, LinkedList *l2, int index);
extern void print(LinkedList *l);
extern int size(LinkedList *l);
extern void clear(LinkedList *l);
extern LinkedList *clone(LinkedList *org);
extern char contains(LinkedList *l, int x);
extern int get(LinkedList *l, int index);
extern int getFirst(LinkedList *l);
extern int getLast(LinkedList *l);
extern int indexOf(LinkedList *l, int x);
extern int lastIndexOf(LinkedList *l, int x);
extern int element(LinkedList *l);
extern void set(LinkedList *l, int index, int x);
extern void removeData(LinkedList *l, int x);
extern void removeAt(LinkedList *l, int index);
extern int *toArray(LinkedList *l);

#endif

LinkedList의 헤더 파일은 Singly LinkedList의 헤더 파일에서 Node의 데이터 멤버 말고는 손댄것이 거의 없다고 볼 수 있다.

 

<LinkedList 구현 파일>

#include <stdio.h>
#include <malloc.h>
#include "LinkedList.h"

Node *allocNode(int data)
{
	Node *tmp = (Node *)malloc(sizeof(Node)); 

	tmp->data = data;
	tmp->prev = tmp;
	tmp->next = tmp;

	return tmp;
}

void insert(Node *node, Node *chain)
{
	node->prev = chain->prev;
	node->next = chain;
	chain->prev->next = node;
	chain->prev = node;
}

void append(Node *node, Node *chain)
{
	node->prev = chain;
	node->next = chain->next;
	chain->next->prev = node;
	chain->next = node;
}

void removeNode(Node *node)
{
	//printf("node->data = %d\n", node->data);
	node->prev->next = node->next;
	node->next->prev = node->prev;
}

/*main()
{
	Node *p;
	Node *q;
	Node *tmp;

	q = allocNode(7);

	tmp = q;
	printf("%d ", tmp->data);
	while (tmp->next != q) {		
		tmp = tmp->next;
		printf("%d ", tmp->data);
	}
	printf("\n");

	p = allocNode(5);
	insert(p, q);
	tmp = q;
	printf("%d ", tmp->data);
	while (tmp->next != q) {
		tmp = tmp->next;
		printf("%d ", tmp->data);
	}
	printf("\n");

	p = allocNode(9);
	insert(p, q);
	tmp = q;
	printf("%d ", tmp->data);
	while (tmp->next != q) {
		tmp = tmp->next;
		printf("%d ", tmp->data);
	}
	printf("\n");

	p = allocNode(8);
	insert(p, q);
	tmp = q;
	printf("%d ", tmp->data);
	while (tmp->next != q) {
		tmp = tmp->next;
		printf("%d ", tmp->data);
	}
	printf("\n");
}*/

void initList(LinkedList *l) 
{
	l->header = NULL;
	l->count = 0;
}

void disposeList(LinkedList *l) 
{
	Node *tmp;
	if (l->header == NULL) return;
	while (l->header->next != l->header) {
		tmp = l->header->next;
		removeNode(tmp);
	}
	removeNode(l->header);
}

void addFirst(LinkedList *l, int x)
{
	add(l, x);
	l->header = l->header->prev;

}

void add(LinkedList *l, int x) 
{
	Node *tmp;

	l->count = l->count + 1;
	if (l->header == NULL) {
		l->header = allocNode(x);
		return;
	}
	tmp = allocNode(x);
	insert(tmp, l->header);
}

void addLast(LinkedList *l, int x)
{
	add(l, x);
}

void addAt(LinkedList *l, int index, int x) 
{
	Node *tmp;
	Node *newNode;
	int i;

	if (index == 0) {
		addFirst(l, x);
		return;
	}
	tmp = l->header;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	newNode = allocNode(x);
	insert(newNode, tmp);
}

void addAllAt(LinkedList *l1, LinkedList *l2, int index)
{
	Node *tmp;
	Node *tmp2;
	Node *newNode;
	int l2Count;
	int i;

	tmp = l1->header;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	tmp2 = l2->header;
	l2Count = l2->count;
	while (l2Count-- > 0) {
		newNode = allocNode(tmp2->data);
		insert(newNode, tmp);
		tmp2 = tmp2->next;
		l1->count++;
	}
	if (index == 0) {
		for (i = 0; i < l2->count; i++) {
			tmp = tmp->prev;
		}
		l1->header = tmp;
	}
}

void print(LinkedList *l) 
{
	Node *tmp;
	
	if (l->header == NULL) {
		printf("[]\n");
		return;
	}
	tmp = l->header;
	printf("[%d", tmp->data);
	while (tmp->next != l->header) {
		tmp= tmp->next;
		printf(" %d", tmp->data);
	}
	printf("]\n");
}

int size(LinkedList *l)
{
	return l->count;
}

void clear(LinkedList *l)
{
	Node *tmp;
	if (l->header == NULL) return;
	while (l->header->next != l->header) {
		tmp = l->header->next;
		removeNode(tmp);
	}
	l->header = NULL;
	l->count = 0;
}

LinkedList *clone(LinkedList *org)
{
	LinkedList *newList;
	Node *tmp;
	Node *newNode;
	int i;

	newList = (LinkedList *)malloc(sizeof(LinkedList));
	initList(newList);

	tmp = org->header;
	for (i = 0; i < org->count; i++) {
		add(newList, tmp->data);
		tmp = tmp->next;
	}
	newList->count = org->count;

	return newList;
}

char contains(LinkedList *l, int x) 
{
	int i;
	Node *tmp;

	tmp = l->header;
	for (i = 0; i < l->count; i++) {
		if (tmp->data == x) return TRUE;
		tmp = tmp->next;
	}

	return FALSE;
}

int get(LinkedList *l, int index) 
{
	int i;
	Node *tmp;

	if (l->header == NULL) return -1;
	tmp = l->header;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	return tmp->data;
}

int getFirst(LinkedList *l) 
{
	if (l->header == NULL) return -1;
	return l->header->data;
}

int getLast(LinkedList *l) 
{
	if (l->header == NULL) return -1;
	return l->header->prev->data;
}

int indexOf(LinkedList *l, int x) 
{
	Node *tmp;
	int pos;
	int i;

	if (l->header == NULL) return -1;
	tmp = l->header;
	pos = 0;
	for (i = 0; i < l->count; i++) {
		if (tmp->data == x) return pos;
		tmp = tmp->next;
		pos++;
	}
	return -1;
}

int lastIndexOf(LinkedList *l, int x)
{
	Node *tmp;
	int pos;
	int i;
	int value = -1;

	if (l->header == NULL) return value;
	pos = 0;
	tmp = l->header;
	for (i = 0; i < l->count; i++) {
		if (tmp->data == x) value = pos;
		tmp = tmp->next;
		pos++;
	}

	return value;
}

int element(LinkedList *l) 
{
	if (l->header == NULL) return -1;
	return l->header->data;
}

void set(LinkedList *l, int index, int x) 
{
	Node *tmp;
	int i;

	if (l->header == NULL) {
		printf("List is empty\n");	
		return;
	}
	tmp = l->header;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	tmp->data = x;
}

void removeData(LinkedList *l, int x)
{
	Node *tmp;
	Node *toDelete;
	int i;

	if (l->header == NULL) {
		printf("List is empty\n");	
		return;
	}
	if (l->header->data == x) {
		if (l->count == 1) {
			toDelete = l->header;
			l->header = NULL;
			l->count = 0;
			free(toDelete);
			return;
		}
		toDelete = l->header;
		l->header = l->header->next;
		l->count = l->count - 1;
		removeNode(toDelete);
		free(toDelete);
		return;
	}
	tmp = l->header;
	for (i = 0; i < l->count; i++) {
		if (tmp->data == x) {
			l->count = l->count - 1;
			toDelete = tmp;
			removeNode(tmp);
			free(toDelete);
			return;
		}
		tmp = tmp->next;
	}

	printf("No such element\n");	
}

void removeAt(LinkedList *l, int index)
{
	Node *tmp;
	Node *toDelete;
	int i;

	if (l->header == NULL) {
		printf("List is empty\n");	
		return;
	}
	if (index > l->count-1) {
		printf("Index error\n");	
		return;
	}
	if (index == 0) {
		if (l->count == 1) {
			toDelete = l->header;
			l->header = NULL;
			l->count = 0;
			free(toDelete);
			return;
		}
		toDelete = l->header;
		l->header = l->header->next;
		l->count = l->count - 1;
		removeNode(toDelete);
		free(toDelete);
		return;
	}
	tmp = l->header;
	l->count = l->count - 1;
	for (i = 0; i < index; i++) {
		tmp = tmp->next;
	}
	removeNode(tmp);
	free(tmp);
}

int *toArray(LinkedList *l)
{
	int *arr;
	Node *tmp;
	int i;

	if (l->count == 0) return NULL;
	arr = (int *)malloc(sizeof(int) * size(l));
	tmp = l->header;

	for (i = 0; i < l->count; i++) {
		arr[i] = tmp->data;
		tmp = tmp->next;
	}

	return arr;
}

구현 파일에서는 prev가 쓰이는 경우를 제외하고는 손 댄 부분이 없다고 할 수 있다.

반응형

'Data Structure' 카테고리의 다른 글

C언어 1차원 배열과 2차원 배열 간단한 정리와 테스트  (0) 2023.04.01
C++ LinkedList 만들기 (version 4 - Doubly LinkedList)  (0) 2023.03.31
C++ LinkedList 만들기 (version 3 - Iterator 구현 및 사용)  (0) 2023.03.27
C# LinkedList 만들기 (Generic type)  (0) 2023.03.26
C++ LinkedList 만들기 (version 2 - LinkedList Template화 하기)  (0) 2023.03.25

관련글

댓글

티스토리툴바