[이중 연결 리스트] c언어 구현

목차

근본은 c언어지...? 나는 c++이 좋아..

이중 연결리스트 ADT

• init(list): list를 초기화해 준다.

 

• add(list, r, e) : list의 순위 r에 원소 e를 추가한다.

 

• delete(list, r) : list의 순위 r에 위치한 원소를 삭제한다.

 

• get(list, r) : list의 순위 r에 위치한 원소를 출력한다.

 

• print(list) : list의 모든 원소를 저장 순위대로 공백없이 출력한다.

-> r은 1부터 시작한다.

 

구현 방향

더미노드를 통해 삭제와 삽입을 편리하게 했다.

여기서 더미노드란 리스트 맨 앞이나 뒤에 노드를 추가하는 것으로 아무 값도 없는 노드를 말하는데

삭제나 삽입 구현 시 메모리의 누수관리에 용이하다.

 

 

 

struct의 생성

typedef struct Node {
	char elem;
	struct Node* next;
	struct Node* prev;
}Node;
//헤드 노드와 테일 노드 존재
typedef struct List {
	 Node* head;
	 Node* tail;
	 Node* cur;
	int size;
}List;

 

초기화 함수

void init(List* list) {
	list->head = (Node*)malloc(sizeof(Node));  //더미노드 생성
	list->tail = (Node*)malloc(sizeof(Node));   //더미노드 생성
	list->head->next = list->tail;  //더미 노드 서로를 가르키도록 초기화
	list->tail->prev = list->head;
	list->cur = NULL;
	list->size = 0;  //사이즈 0으로 초기화
}

 

삽입 함수

void add(List* list, int r, char e) {
	Node* newNode = (Node*)malloc(sizeof(Node));  //새로운 노드의 생성
	newNode->elem = e;   

	if (r > list->size + 1) {    //사이즈를 벗어난 위치 삽입일 경우 
		printf(" invalid position\n"); 
		return 0 ;
	}
	if (list->head->next == list->tail) {  //더미노드만 있을 경우
		list->head->next = newNode;
		list->tail->prev = newNode;
		newNode->next = list->tail; 
		newNode->prev = list->head;
	}
	else {
		r -= 1;  //인덱스가 1부터 시작하므로 하나 줄여야 한다
		list->cur = list->head->next;  //더미노드 다음 노드가 첫 노드
		while (r--) {
			list->cur = list->cur->next;  //r만큼 이동해서 원하는 위치 안착
		}
		newNode->prev = list->cur->prev; //삽입 시에 앞 뒤로 노드를 잘 연결해 주어야 한다
		list->cur->prev->next = newNode;
		newNode->next = list->cur;
		list->cur->prev = newNode;
	}
	list->size++;  //사이즈 증가
}

 

삭제 함수

void delete(List *list, int r) {
	if (r > list->size) {   //사이즈를 벗어난 위치의 삭제일 경우
		printf(" invalid position\n");
		return;
	}
	r -= 1;  //인덱스가 1부터 시작하므로 하나 줄여야 한다
	list->cur = list->head->next;
	while (r--) {
		list->cur = list->cur->next; //r만큼 이동해서 원하는 위치 안착
	}
	Node* delnode = list->cur;  //삭제할 노드
	char del = delnode->elem;  
	list->cur->next->prev = list->cur->prev;   //삭제 시에 삭제노드를 제외한 양 옆의
	list->cur->prev->next = list->cur->next;  //노드를 연결해 주어야 함
	
	list->cur = list->cur->prev;    //가르키는 곳 위치 바꿔줘야함
	free(delnode);

	list->size--;  //사이즈 감소
}

 

get함수

void get(List* list, int r) {
	if (r > list->size) {   //사이즈를 벗어난 원소를 가르킬 경우
		printf(" invalid position\n");
		return 0;
	}
	r -= 1;  //인덱스가 1부터 시작하므로 하나 줄여야 한다
	list->cur = list->head->next;
	while (r--) {  //r만큼 이동해서 원하는 위치 안착
		list->cur = list->cur->next;  
	}
	printf("%c\n", list->cur->elem);
}

 

print함수

void print(List* list) {
	if (list->size == 0)  //사이즈가 0일 경우
	{
		printf(" invalid position\n");
		return 0;
	}
	list->cur = list->head->next;
	int len = list->size;
	while (len--) {
		printf("%c", list->cur->elem);
		list->cur = list->cur->next;
	}
	printf("\n");
}

 

메모리 누수가 너무 싫다...