단일 연결리스트 / 양방향 연결 리스트

Notice

Recent Posts

Recent Comments

Link

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

DNF LOVE

단일 연결리스트 / 양방향 연결 리스트 본문

Computer Science/자료구조

단일 연결리스트 / 양방향 연결 리스트

botho 2019. 10. 23. 21:12

1. 단방향 연결리스트

typedef struct ListNode{
	int data;
	struct ListNode* next;

}ListNode;

ListNode* Add(int data);

void AppendNode(ListNode** Head, ListNode* new_Node);

void Serach(ListNode** Head);

void Delete(ListNode **Head, int data);

void insertNode(ListNode **Head, int data);

ListNode* Add(int data) {
	ListNode* new_Node = (ListNode*)malloc(sizeof(ListNode));
	
	new_Node->data = data;
	new_Node->next = NULL;
	
	return new_Node;
}

void AppendNode(ListNode** Head, ListNode* new_Node) {
	ListNode* Tail;

	if ((*Head) == NULL) {
		*Head = new_Node;
	}

	else {
		Tail = (*Head);

		while (!(Tail->next == NULL)) {
			Tail = Tail->next;
		}
		Tail->next = new_Node;
	}
}



void Serach(ListNode** Head) {
	ListNode* Node = (ListNode*)malloc(sizeof(ListNode));

	if ((*Head) == NULL) {
		printf("Not Data!\n");
		exit(1);
	}

	else {
		Node = (*Head);
		while (!(Node == NULL)) {
			printf("Node->data : %d\n", Node->data);
			Node = Node->next;
		}
	}
}



void Delete(ListNode **Head, int data) {
	ListNode* deleteNode = NULL;
	ListNode* Node = NULL;

	if (*Head == NULL) {
		printf("Not Data!\n");
		return;
	}

	deleteNode = *Head;
	deleteNode = deleteNode->next;
	Node = *Head;

	while (!(deleteNode == NULL)) {
		if ((deleteNode->data) == data) {
			Node->next = deleteNode->next;
			free(deleteNode);
			break;
		}

		Node = deleteNode;
		deleteNode = deleteNode->next;
	}
}



void insertNode(ListNode** Head, ListNode *newNode, int search_data) {

	ListNode* insertNode = NULL;
	ListNode* Node = NULL;

	if (*Head == NULL) {
		printf("Not Data!\n");
		return;
	}

	insertNode = *Head;
	insertNode = insertNode->next;
	Node = *Head;

	while (!(insertNode == NULL)) {
		if (insertNode->data == search_data) {
			newNode->next = Node->next;
			Node->next = newNode;
			break;
		}
	}
}

int main(void)
{
	ListNode* head = NULL;
	ListNode* new_Node = NULL;
	new_Node = Add(0);
	AppendNode(&head, new_Node);
	new_Node = Add(1);
	AppendNode(&head, new_Node);
	new_Node = Add(2);
	AppendNode(&head, new_Node);
	Serach(&head);
	new_Node = Add(3);
	insertNode(&head, new_Node, 1);
	Serach(&head);
}

1-2. 단방향 연결리스트(tail 존재 o)

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>

// 동적 메모리 할당 설명을 위한 코드
typedef struct _node {
	int data;
	struct _node *next;
} Node;

int main()
{
	Node *head = NULL;
	Node *tail = NULL;
	Node *cur = NULL;

	Node *newNode = NULL;

	int readdata;

	// 데이터를 입력받는 과정
	while(1) {

		printf("자연수 입력 : ");				// 데이터를 담을 공간
		scanf_s("%d", &readdata);					// 연결의 도구

		if (readdata < 1) {
			break;
		}

		// 노드의 추가 과정
		newNode = (Node*)malloc(sizeof(Node));	// 노드에 메모리 할당
		newNode->data = readdata;				// 새로운 노드에 입력한 데이터 집어넣기
		newNode->next = NULL;					// 이 노드의 다음 포인트는 Null을 가리킴

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

		tail = newNode;							// 노드의 끝을 Tail이 가리키게 함.
	}
	printf("\n");

	// 입력 받은 데이터의 출력 과정
	printf("입력 받은 데이터의 전체 출력! \n");
	if (head == NULL) {
		printf("저장된 자연수가 존재하지 않습니다. \n");
	}
	else {
		cur = head;
		printf("%d ", cur->data);

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

	// 메모리 해제
	if (head == NULL) {
		return 0;
	}
	else {
		Node *delNode = head;
		Node *delnextNode = head->next;

		printf("%d를 삭제합니다. \n", head->data);
		free(delNode);

		while (delnextNode != NULL) {
			delNode = delnextNode;
			delnextNode = delnextNode->next;

			printf("%d를 삭제합니다. \n", delNode->data);
			free(delNode);
		}
	}

	return 0;
}

1-3. 단일 연결리스트(tail 존재 xx)

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Ldata;

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

typedef struct _linkedList
{
	Node *head;
	Node *cur;
	Node *before;
	int numofdata;
	int (*comp)(Ldata d1, Ldata d2);
} LinkedList;

typedef LinkedList List;

void ListInit(List *plist);

void LInsert(List *plist, Ldata data);

void FInsert(List *plist, Ldata data);

void SInsert(List *plist, Ldata data);

int LFirst(List *plist, Ldata *pdata);

int LNext(List *plist, Ldata *pdata);

Ldata LRemove(List *plist);

int LCount(List *plist);

void SetSortRule(List *plist, int(*comp)(Ldata d1, Ldata d2));

#endif

#include "pch.h"
#include "DLinkedList.h"
#include <stdlib.h>
#include <stdio.h>

void ListInit(List *plist) {				// 리스트 초기화
	// Head에 메모리 할당(데이터는 들어있지 않는 더미 데이터)
	plist->head = (Node*)malloc(sizeof(Node));
	// 더미데이터(해드)의 다음 노드(첫 데이터 노드) Null 할당
	plist->head->next = NULL;
	plist->comp = NULL;
	plist->numofdata = 0;
}

void LInsert(List *plist, Ldata data) {		// 노드 추가(새로운 데이터를 더미데이터 다음에 추가)

	// 새 노드 메모리 할당
	Node *newnode = (Node*)malloc(sizeof(Node));
	// 새로운 노드에 입력한 데이터 넣기
	newnode->data = data;

	// 새 노드가 다른 노드를 가리키게 한다.
	newnode->next = plist->head->next;
	// 더미 노드가 새 노드를 가리키게 한다.
	plist->head->next = newnode;

	// 저장된 노드의 수를 하나 증가시킴
	(plist->numofdata)++;

}

int LFirst(List *plist, Ldata *pdata) {					// 첫 노드로 돌아가기
	
	// 더미 노드가 NULL을 가리킨다면
	if (plist->head->next == NULL) {
		// 반환할 것이 없다.
		return FALSE;
	}

	// Before는 더미 노드를 가리키게 한다.
	plist->before = plist->head;
	// cur는 첫 번째 노드(더미 노드 다음)을 가리키게 한다.
	plist->cur = plist->head->next;

	// 첫 번째 노드의 데이터를 전달하는 매개포인터 pdata로 해당 데이터가 넘겨진다.
	*pdata = plist->cur->data;
	// 반환 성공
	return TRUE;
}

int LNext(List *plist, Ldata *pdata) {		// 다음 노드 받아오기

	// 현재노드의 다음 노드가 NULL을 가리킨다면
	if (plist->cur->next == NULL) {
		// 반환할 것이 없음
		return FALSE;
	}

	// 이전 커서는 현재 노드를 가리키고
	plist->before = plist->cur;
	// 현재 커서(반환하고자 하는 노드 위치)는 다음 노드를 가리킨다.
	plist->cur = plist->cur->next;

	// 반환하고자 하는 데이터를 가리키는 매개 포인터 pdata
	*pdata = plist->cur->data;

	// 반환 성공
	return TRUE;
}

Ldata LRemove(List *plist) {				// 해당 노드 삭제
	
	// 현재 노드의 위치를 가져오는 rpos포인터
	Node *rpos = plist->cur;
	// 현재 노드의 데이터를 가져오는 rdata
	Ldata rdata = rpos->data;

	// before의 다음은, 현재 위치의 다음을 가리킨다(한 자리씩 앞당긴다)
	plist->before->next = plist->cur->next;
	// Cur는 before을 가리킨다(한 자리씩 앞당겨진다)
	plist->cur = plist->before;

	// 삭제되는 데이터 메모리 반환
	free(rpos);
	// numofdata 1 줄이기
	(plist->numofdata)--;
	
	// 반환 성공하면 해당 데이터를 반환
	return rdata;
}

int LCount(List *plist) {					// 현재 데이터 수 반환
	return plist->numofdata;
}

#pragma region 일반 더미 노드를 가지고 있는 링크드 리스트
int main() {

	// 리스트 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	// 데이터 저장
	LInsert(&list, 11); LInsert(&list, 22);
	LInsert(&list, 33); LInsert(&list, 44);
	LInsert(&list, 55); LInsert(&list, 22);

	// 저장된 데이터 전체 출력
	printf("현재 데이터 수 : %d \n", LCount(&list));

	if (LFirst(&list, &data)) {
		printf("%d ", data);		// pdata로부터 데이터를 전해받은 data

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

	printf("\n\n");

	// 숫자 22를 검색하여 전부 삭제
	if (LFirst(&list, &data)) {

		if (data == 22) {
			LRemove(&list);
		}

		while (LNext(&list, &data)) {
			if (data == 22) {
				LRemove(&list);
			}
		}
	}

	// 삭제 후 남아있는 데이터 전체 출력
	printf("현재 데이터 수 : %d \n", LCount(&list));

	if (LFirst(&list, &data)) {
		printf("%d ", data);		// pdata로부터 데이터를 전해받은 data

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

	return 0;
}
#pragma endregion

2. 양방향 연결 리스트

#include "pch.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

struct Node {
	int data;
	Node* next, *prev;
	Node() {
		next = prev = NULL;
		data = 0;
	}
	Node(int i, Node *ptr) { // ptr 뒤에 추가한다
		data = i;
		prev = ptr;
		next = ptr->next;
		next->prev = prev->next = this;
	}
	void selvDelete() {
		prev->next = next;
		next->prev = prev;
		delete this;
	}
};

struct DLinkedList {
	Node *head;
	Node *tail;
	int count;
	DLinkedList() { // 생성자
		count = 0;
		head = new Node(); // 더미 선언 및 가지고있기
		tail = new Node();
		head->next = tail; // 서로 연결
		tail->prev = head;
	}
	~DLinkedList() { // 소멸자
		while (head->next != tail) {
			head->next->selvDelete();
		}
		delete head;
		delete tail;
	}

	void firstInsert(int i) {
		// head다음에 추가한다
		new Node(i, head);
	}
	void endInsert(int i) {
		// tail 앞에 추가한다
		new Node(i, tail->prev);
	}
	void firstDelete() { 
		// head다음 노드 삭제한다
		if (head->next == tail) {
			return;
		}
		head->next->selvDelete;
	}
	void endDelete() {
		//tail 앞에 제거한다.
		if (tail->prev == head) {
			return;
		}
		tail->prev->selvDelete();
	}

	void printAll() {
		Node * temp = head;
		while (temp->next != tail) {
			printf("%d\n", temp->next->data);
			temp = temp->next;
		}
	}
};

int main(void)
{
	DLinkedList *list = new DLinkedList();
	list->firstInsert(1); //1을 삽입한다.(가장앞)
	list->firstInsert(3); //3을 삽입한다.(1앞에)
	list->firstInsert(5); //5을 삽입한다.(3앞에)
	list->firstDelete(); //5를 삭제한다
	list->endInsert(100); //100을 삽입한다.(가장뒤에)
	list->endInsert(200); //200을 삽입한다.(100뒤에)
	list->endInsert(300); //300을 삽입한다.(200뒤에)
	list->endDelete(); //300을 삭제한다.
	list->printAll();
	delete list;
}

저작자표시 동일조건

'Computer Science > 자료구조' 카테고리의 다른 글

[자료구조] 고급 자료구조 Set, Hash, HashMap, HashTable, 해쉬충돌, 해쉬함수 에 대해서 (0)	2019.10.23
[자료구조 - 그래프의 순환] 코딩 테스트의 꽃 그래프의 순환 BFS와 DFS (0)	2019.09.20
[자료구조 - 트리] 그래프의 일종인 트리의 정의와 특징에 대해 알아보자(비공개) + Graph Modeling (0)	2019.09.20
[자료구조 - 그래프의 주기] 방향 그래프와 무방향 그래프(SCC, BCC의 개념) (0)	2019.09.20
[자료구조 - 그래프] 그래프(Graph)의 정의와 종류 (0)	2019.09.20

'Computer Science/자료구조' Related Articles

DNF LOVE

단일 연결리스트 / 양방향 연결 리스트 본문

단일 연결리스트 / 양방향 연결 리스트

'Computer Science > 자료구조' 카테고리의 다른 글

티스토리툴바