#09 자료구조 양방향연결리스트

양방향 연결리스트

Main.h

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

int main(void)
{
	// 양방향 연결 리스트의 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	// 8개의 데이터 저장
	LInsert(&list, 1); LInsert(&list, 2);
	LInsert(&list, 3); LInsert(&list, 4);
	LInsert(&list, 5); LInsert(&list, 6);
	LInsert(&list, 7); LInsert(&list, 8);

	// 저장된 데이터의 조회
	if (LFirst(&list, &data))
	{
		printf("%d ", data);

		// 오른쪽 노드로 이동하며 데이터 조회
		while (LNext(&list, &data))
			printf("%d ", data);

		// 왼쪽 노드로 이동하며 데이터 조회
		while (LPrevious(&list, &data))
			printf("%d ", data);

		printf("\n\n");
	}

	return 0;
}

 

DBLinkedList.h

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

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

typedef struct _DBLinkedList
{
	Node* head;
	Node* cur;
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List* plist);
void LInsert(List* plist, Data data);

int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
int LPrevious(List* plist, Data* pdata);
int LCount(List* plist);

#endif

 

DBLinkedList.c

구현해보기

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

void ListInit(List* plist)
{

}
void LInsert(List* plist, Data data)
{

}

int LFirst(List* plist, Data* pdata)
{

}
int LNext(List* plist, Data* pdata)
{

}
int LPrevious(List* plist, Data* pdata)
{

}
int LCount(List* plist)
{

}

구현

#ifdef _MSC_YER
#define _CRT_SECURE_NO_WARNINGS
#endif

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

void ListInit(List* plist)
{
	plist->head = NULL;
	plist->numOfData = 0;
}

void LInsert(List* plist, Data data) // 첫 번째 노드의 추가 과정만 담음
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	// 아래 문장에서 plist->head는 NULL이다!
	newNode->next = plist->head; // 새 노드의 next를 NULL로 초기화
	if (plist->head != NULL)
		plist->head->prev = newNode; // 두 번째 이후의 노드를 추가할 때만 실행
	newNode->prev = NULL; // 새 노드의 prev를 NULL로 초기화
	plist->head = newNode; // 포인터 변수 head가 새 노드 가리키게 함

	(plist->numOfData)++;
}

int LFirst(List* plist, Data* pdata)
{
	if (plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;
	*pdata = plist->cur->data;

	return TRUE;
}

int LNext(List* plist, Data* pdata)
{
	if (plist->cur->next == NULL)
		return FALSE;

	plist->cur = plist->cur->next;
	*pdata = plist->cur->data;

	return TRUE;
}

int LPrevious(List* plist, Data* pdata)
{
	if (plist->cur->prev == NULL)
		return FALSE;

	plist->cur = plist->cur->prev;
	*pdata = plist->cur->data;

	return TRUE;
}

int LCount(List* plist)
{
	return plist->numOfData;
}