원형 연결 리스트와 양방향 연결 리스트

원형 연결 리스트는 메모리를 순환적으로 사용가능하게 해주는데
단순 연결 리스트에서 마지막 노드가 처음 노드를 가리키게 하면 이것이 바로 원형 연결리스트이다.

원형 연결리스트는 꼬리와 머리의 구분이 없으며, 따라서 단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다.

그리고 꼬리만 있어도 머리는 쉽게 알 수 있으므로 tail만 있어도 된다.
이를 변형된 원형 연결리스트라 한다.

변형된 원형 연결리스트의 헤더 파일

#ifndef C_LINKED_LIST_H
#define C_LINKED_LIST_H

#define TRUE 1
#define FALSE 0

typedef int Data;

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

typedef struct _CLL
{
Node tail;
Node cur;
Node * before;
int numOfData;
} CList;

typedef CList List;

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

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

#endif

함수가 정의된 소스파일

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

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

void LInsertFront(List plist, Data data)
{
Node newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;

if(plist->tail == NULL) //데이터가 없을 때
{
	plist->tail = newNode;
	newNode->next = newNode;//원형 연결리스트이므로
}
else
{
	newNode->next = plist->tail->next;
	plist->tail->next = newNode;
}//처음에 1이 있다고 가정
1이 tail, tail의 next도 1, 2가 추가되면 1은 그대로 tail, 2의 next는 1, 1dml next는 2
이후 여러개일 때는 newnode의 next는 기존 taildml next, 즉, 기존 헤드를 가리키고, newnode는 새로운 헤드가 된다.

(plist->numOfData)++;

}

void LInsert(List plist, Data data)
{
Node newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;

if(plist->tail == NULL) 
{
	plist->tail = newNode;
	newNode->next = newNode;//똑같이 원형리스트이므로
}
else 
{
	newNode->next = plist->tail->next;//뉴노드의 넥스트는 헤드
	plist->tail->next = newNode;//기존 tail의 next는 뉴노드
	plist->tail = newNode;//뉴노드가 새로운 테일이 된다.
}

(plist->numOfData)++;

}

int LFirst(List plist, Data pdata)
{
if(plist->tail == NULL) // 저장된 노드가 없다면
return FALSE;

plist->before = plist->tail;
plist->cur = plist->tail->next;

*pdata = plist->cur->data;
return TRUE;

}

int LNext(List plist, Data pdata)
{
if(plist->tail == NULL) // 저장된 노드가 없다면
return FALSE;

plist->before = plist->cur;
plist->cur = plist->cur->next;

*pdata = plist->cur->data;
return TRUE;

}

Data LRemove(List plist)
{
Node rpos = plist->cur;
Data rdata = rpos->data;

if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
{
	if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
		plist->tail = NULL;
	else
		plist->tail = plist->before;
}

plist->before->next = plist->cur->next;
plist->cur = plist->before;

free(rpos);
(plist->numOfData)--;
return rdata;

}

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

결국 핵심은 하나 남으면 tail의 next가 tail이라는 것

양방향 연결리스트

prev가 생겨 그 전으로 돌아갈 수 있다는게 핵심이다.
헤더에도 LPrevious가 추가되었다.

헤더파일

#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

소스 파일

#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;

newNode->next = plist->head;
if(plist->head != NULL)
	plist->head->prev = newNode;

newNode->prev = NULL;
plist->head = newNode;

(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;
}