[자료구조] 환형 링크드 리스트(Circular Linked List)

환형 링크드 리스트란

원 형태의 자료구조.

환형 더블 링크드 리스트로써 더블 링크드 리스트를 업그레이드 한 자료구조.

헤드와 테일이 연결 된 구조.

리스트 세계의 우로보로스라는 전설속 뱀을 뜻하기도 한답니다.

테일이 없이 계속 이어져 있다고 생각하면 됩니다.

C 소스

CircularLinkedList.h

/*

* CirtularLinkedList.h

*

* Created on: 2018. 12. 30.

* Author: otrodevym

*/

#ifndef CIRTULARLINKEDLIST_H_

#define CIRTULARLINKEDLIST_H_

#define NULL (void *)0

#include <stdio.h>

#include <stdlib.h>

typedef int ElementType;

typedef struct tagNode{

    ElementType Data;

    struct tagNode* PrevNode;

    struct tagNode* NextNode;

} Node;

Node* CDLL_CreateNode(ElementType NewData);

void CDLL_DestroyNode(Node* Node);

void CDLL_AppendNode(Node** Head, Node* NewNode);

void CDLL_InsertAfter(Node* Current, Node* NewNode);

void CDLL_RemoveNode(Node** Head, Node* Remove);

Node* CDLL_GetNodeAt(Node* Head, int Location);

int CDLL_GetNodeCount(Node* Head);

#endif /* CIRTULARLINKEDLIST_H_ */

추가 기능을  주의 깊게 봅니다.

void CDLL_AppendNode(Node** Head, Node* NewNode) {

    if ((*Head) == NULL) {

        *Head = NewNode;

        (*Head)->NextNode = *Head;

        (*Head)->PrevNode = *Head;

    } else {

        Node *Tail = (*Head)->PrevNode;

        Tail->NextNode->PrevNode = NewNode;

        Tail->NextNode = NewNode;

        NewNode->NextNode = (*Head);

        NewNode->PrevNode = Tail;

    }

}

CircularLinkedList.c

/*

* CirtularLinkedList.c

*

* Created on: 2018. 12. 30.

* Author: otrodevym

*/

#include "./CircularLinkedList.h"

Node* CDLL_CreateNode(ElementType newData) {

    Node* NewNode = (Node*) malloc(sizeof(Node));

    NewNode->Data = newData;

    NewNode->PrevNode = NULL;

    NewNode->NextNode = NULL;

    return NewNode;

}

void CDLL_DestroyNode(Node* Node) {

    free(Node);

}

void CDLL_AppendNode(Node** Head, Node* NewNode) {

    if ((*Head) == NULL) {

        *Head = NewNode;

        (*Head)->NextNode = *Head;

        (*Head)->PrevNode = *Head;

    } else {

        Node *Tail = (*Head)->PrevNode;

        Tail->NextNode->PrevNode = NewNode;

        Tail->NextNode = NewNode;

        NewNode->NextNode = (*Head);

        NewNode->PrevNode = Tail;

    }

}

void CDLL_InsertAfter(Node* Current, Node* NewNode) {

    NewNode->NextNode = Current->NextNode;

    NewNode->PrevNode = Current;

    Current->NextNode->PrevNode = NewNode;

    Current->NextNode = NewNode;

}

void CDLL_RemoveNode(Node** Head, Node* Remove){

    if( *Head == NULL){

        (*Head)->PrevNode->NextNode = Remove->NextNode;

        (*Head)->NextNode->PrevNode = Remove->PrevNode;

        *Head = Remove->NextNode;

        Remove->PrevNode = NULL;

        Remove->NextNode = NULL;

    }else{

        Node* Temp = Remove;

        Remove->PrevNode->NextNode = Temp->NextNode;

        Remove->NextNode->PrevNode = Temp->PrevNode;

        Remove->PrevNode = NULL;

        Remove->NextNode = NULL;

    }

}

Node* CDLL_GetNodeAt(Node* Head, int Location){

    Node* Current = Head;

    while(Current != NULL && (--Location) >=0){

        Current = Current->NextNode;

    }

    return Current;

}

int CDLL_GetNodeCount(Node* Head){

    unsigned int Count = 0;

    Node* Current = Head;

    while(Current != NULL ){

        Current = Current->NextNode;

        Count++;

        if(Current == Head){

            break;

        }

    }

    return Count;

}

void PrintNode(Node* _Node){

    if(_Node->PrevNode == NULL){

        printf("prev : NULL");

    }else{

        printf("prev : %d ", _Node->PrevNode->Data);

    }

    printf(" Current : %d ", _Node->Data);

    if(_Node->NextNode == NULL){

        printf("Next : NULL \n");

    }else{

        printf("Next : %d \n", _Node->NextNode->Data);

    }

}

main.c

/*

* main.c

*

* Created on: 2018. 12. 30.

* Author: otrodevym

*/

#include "CircularLinkedList.h"

int main(int argc, char *argv[]){

    printf("hello");

    int i = 0;

    int Count = 0;

    Node* List = NULL;

    Node* NewNode = NULL;

    Node* Current = NULL;

    for(i = 0; i < 5; i++){

        NewNode = CDLL_CreateNode(i);

        CDLL_AppendNode(&List, NewNode);

    }

    Count = CDLL_GetNodeCount(List);

    for(i = 0; i < Count; i++){

        Current = CDLL_GetNodeAt(List, i);

        printf("List [%d] : %d \n", i, Current->Data);

    }

    printf(" \n INserting 3000 After [2]... \n");

    Current = CDLL_GetNodeAt(List, 2);

    NewNode = CDLL_CreateNode(3000);

    CDLL_InsertAfter(Current,NewNode);

    Count = CDLL_GetNodeCount(List);

    for(i = 0; i < Count*2; i++){

        if(i == 0){

            Current = List;

        }else{

            Current = Current->NextNode;

        }

        printf("List [%d] : %d \n", i, Current->Data);

    }

    printf("\n Destroying List... \n");

    Count = CDLL_GetNodeCount(List);

    for(i = 0; i< Count; i++){

        Current = CDLL_GetNodeAt(List, i );

        if(Current != NULL){

            CDLL_RemoveNode(&List, Current);

            CDLL_DestroyNode(Current);

        }

    }

return 0;

}

자바 소스

package linked_list;

public class CircularLinkedList<T> {

    private int size;

    private Node head;

    

    class Node{

        private T value;

        private Node prevNode;

        private Node nextNode;

        

        public Node(T value) {

            this.value = value;

            this.prevNode = null;

            this.nextNode = null;

        }

    }

    public CircularLinkedList() {

        this.size = 0;

        this.head = null;

    }

    

    

    private void add(T value) {

        Node newNode = new Node(value);

        if(this.head == null) {

            this.head = newNode;

            this.head.nextNode = newNode;

            this.head.prevNode = newNode;

        }else {

            

            Node current = this.head;

            

            current.prevNode.nextNode = newNode;

            newNode.prevNode = current.prevNode;

            

            newNode.nextNode = this.head;

            this.head.prevNode= newNode;

        }

        this.size++;

    }

    

    private void remove(int index) {

        Node current = this.head;

        while(current.nextNode != null && (--index) >=0) {

            current = current.nextNode;

        }

        current.nextNode.prevNode = current.prevNode;

        current.prevNode.nextNode = current.nextNode;

        current.nextNode = null;

        current.prevNode = null;

        

        this.size--;

    }

    

    private T get(int index) {

        Node current = this.head;

        if(0 == index) {

            

//          환형 링크드 리스트는 계속 돌아야 맞음

//      }else if(index == (size-1)) {

//          while(current.nextNode != null && (--index) >= 0) {

//              current = current.nextNode;

//          }

        }else {

            while(current.nextNode != null && (--index) >= 0) {

                current = current.nextNode;

            }

        }

        return current.value;

    }

    

    private void update(int index, T value) {

        Node current = this.head;

        while(current.nextNode != null && (--index) >= 0){

            current = current.nextNode;

        }

        

        current.value = value;

        

    }

    private void print() {

        for(int i = 0; i < size; i++) {

            System.out.println(this.get(i));

        }

    }

    public static void main(String args[]) {

        CircularLinkedList<String> list = new CircularLinkedList<>();

        list.add("1");

        list.add("2");

        list.add("3");

        list.add("4");

        list.print();

        System.out.println("----------");

        

        list.remove(1);

        list.print();

        System.out.println("----------");

        

        list.update(1, "100");

        list.print();

        System.out.println("----------");

        

        list.update(3, "100");

        list.print();

        System.out.println("----------");

    }

}