자료구조 :: 양방향 원형 연결리스트

LinkedListType.h

/*
 * =====================================================================================
 *
 *       Filename:  LinkedListType.h
 *
 *    Description:  LinkedList Library
 *
 *        Version:  1.0
 *        Created:  2009년 12월 31일 09시 52분 30초
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Yeonjae Kim (https://hisjournal.net), 6l4ck3y3 (at) gmail.com
 *        Company:  CERT-IS
 *
 * =====================================================================================
 */

#ifndef _LINKEDLISTTYPE
#define _LINKEDLISTTYPE

/*-----------------------------------------------------------------------------
 *  List ADT Type
 *----------------------------------------------------------------------------*/
// Define element type.
typedef int element;

typedef struct ListNode {
    element data;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct LinkedListType {
    ListNode *node;
    int length;
} LinkedListType;

/*-----------------------------------------------------------------------------
 *  List ADT Function
 *----------------------------------------------------------------------------*/
/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  error
 *  Description:  Exit after displaying error message.
 *    Parameter:  *mesg - error message
 *       Retuen:  
 * =====================================================================================
 */
void error (char *mesg);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  init
 *  Description:  Initialize list.
 *    Parameter:  L - list
 *       Retuen:  
 * =====================================================================================
 */
void init (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  is_empty
 *  Description:  Return if list is empty.
 *    Parameter:  L - l
 *       Retuen:  If list is empty, this returns 1.
 *                Otherwise 0.
 * =====================================================================================
 */
int is_empty (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  is_in_list
 *  Description:  Return if the item is in list.
 *      Parameter:  L - list
 *                item - stuff to find
 *       Retuen:  If the item is in list, this returns 1.
 *                Otherwise 0.
 * =====================================================================================
 */
int is_in_list (LinkedListType *L, element item);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  get_length
 *  Description:  Get number of element in list.
 *      Parameter:  L - list
 *         Return:  number 0f element in list
 * =====================================================================================
 */
int get_length (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  get_node
 *  Description:  Get the reference of node.
 *      Parameter:  L - list
 *         Return:  reference that is at position
 *                If it isn't in list, this returns NULL.
 * =====================================================================================
 */
ListNode* get_node (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  get_next_node
 *  Description:  Get the reference of next node.
 *      Parameter:  L - list
 *         Return:  reference that is at position
 *                If it isn't in list, this returns NULL.
 * =====================================================================================
 */
ListNode* get_next_node (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  get_prev_node
 *  Description:  Get the reference of prev node.
 *      Parameter:  L - list
 *         Return:  reference that is at position
 *                If it isn't in list, this returns NULL.
 * =====================================================================================
 */
ListNode* get_prev_node (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  insert_node
 *  Description:  Insert a new node at next of the node.
 *      Parameter:  L - list
 *             :  data - data of a new node
 *         Return:
 * =====================================================================================
 */
void insert_node (LinkedListType *L, element data);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  remove_node
 *  Description:  Remove the node.
 *      Parameter:  L - list
 *         Return:
 * =====================================================================================
 */
void remove_node (LinkedListType *L);

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  replace
 *  Description:  Change the data of node.
 *      Parameter:  L - list
 *             :  data - new value of data
 *         Return:
 * =====================================================================================
 */
void replace (LinkedListType *L, element data);

#endif

LinkedListType.c

/*
 * =====================================================================================
 *
 *       Filename:  LinkedLinkedListType.c
 *
 *    Description:  LinkedList Library
 *
 *        Version:  1.0
 *        Created:  2009년 10월 13일 12시 09분 12초
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Yeonjae Kim (https://hisjournal.net/blog), 6l4ck3y3 (at) gmail.com
 *        Company:  CERT-IS (http://www.cert-is.com)
 *
 * =====================================================================================
 */

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

#include "LinkedListType.h"

void error (char *mesg)
{
    fprintf (stderr, "%s\n", mesg);
    exit (1);
}

void init (LinkedListType *L)
{
    L->node = NULL;
    L->length = 0;
}

int is_empty (LinkedListType *L)
{
    return L->node == NULL;
}

int is_in_list (LinkedListType *L, element item)
{
    ListNode *node;

    if (is_empty (L))
    {
        node = (L->node)->next;
        while ((node->data != item) && (node != L->node)) 
            node = node->next;

        if (node == L->node)
        {
            if (node->data != item) return 0;
        }
        
        return 1;
    }

    return 0;
}

int get_length (LinkedListType *L)
{
    return L->length;
}

ListNode* get_node (LinkedListType *L)
{
    return L->node;
}

ListNode* get_next_node (LinkedListType *L)
{
    if (L->node == NULL) return NULL;

    L->node = L->node->next;

    return L->node;
}

ListNode* get_prev_node (LinkedListType *L)
{
    if (L->node == NULL) return NULL;

    L->node = L->node->prev;

    return L->node;
}

void insert_node (LinkedListType *L, element data)
{
    ListNode *p;
    ListNode *new;
    
    new = (ListNode *) malloc (sizeof (ListNode));
    if (new == NULL) error ("Memory allocation error.");

    new->data = data;

    p = get_node (L);
    if (L->node == NULL)
    {
        new->next = new;
        new->prev = new;
        L->node = new;
    }
    else
    {
        new->next = p->next;
        new->prev = p;
        (new->next)->prev = new;
        (new->prev)->next = new;
    }

    if (p == L->node) L->node = new;

    (L->length)++;
}

void remove_node (LinkedListType *L)
{
    ListNode *node;

    if (!is_empty (L))
    {
        node = get_node (L);
        
        (node->prev)->next = node->next;
        (node->next)->prev = node->prev;

        L->node = node->prev;

        if (node == L->node) L->node = NULL;
        free (node);
        (L->length)--;
    }
}

void replace (LinkedListType *L, element data)
{
    ListNode *node = get_node (L);
    if (node == NULL) error ("Memory NULL error.");

    node->data = data;
}

참고문헌