LinkedList(3) 원형연결리스트

원형 연결리스트란, 리스트의 끝과 처음이 연결되어 참조하는 형식의 연결리스트를 말한다.

출처:https://www.geeksforgeeks.org/circular-singly-linked-list-insertion/

위 그림과 같이 연결의 형태가 원을 이루는 것을 원형연결리스트라고 부른다.

기존 연결리스트에서 head대신 tail을 사용하고 tail->next가 첫번째 노드를 가리키게 하면 된다.

 

-ADT

 

ADT는 크게 달라진 것이 없다.

 

void Linsert --> 새 노드를 뒤에 추가

void LFinsert --->새 노드 처음에 추가

void Linit

 

int LFirst

int Lnext

Ldata LRemove

int Lcount

 

- C언어 구현

 

헤더

#ifndef Circular_LinkedList

#define Circular_LinkedList

#define false 0

#define true 1

typedef int Ldata;

typedef struct _node{

    Ldata data;

    struct _node* next;

}Node;

typedef struct _Circle{

    Node* tail;

    Node* before;

    Node* cur;

    int size;

}Circle;

typedef Circle List;

void Linsert(List* plist,Ldata data);

void Linit(List* plist);

void LinsertFirst(List* plist,Ldata data);

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

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

Ldata LRemove(List* plist);

int Lcount(List* plist);

#endif

소스

#include<stdio.h>

#include<stdlib.h>

#include"Circular_LinkedList.h"

void Linsert(List* plist,Ldata data){

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

    newnode->data = data;

    if(plist->tail == NULL){

        newnode->next= newnode;

        plist->tail = newnode;

    }else{

    newnode->next = plist->tail->next;

    plist->tail->next = newnode;

    plist->tail = newnode; //앞에 데이터 넣는것과 뒤에 데이터를 넣는 것에 차이점

    }

    (plist->size)++;

}

void Linit(List* plist){

    plist->size =0;

    plist->cur = NULL;

    plist->before= NULL;

    plist->tail =NULL;

}

void LinsertFirst(List* plist,Ldata data){

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

    newnode->data = data;

    if(plist->tail == NULL){ //여기는 한 방향 연결리스트와 다름

        newnode->next= newnode;

        plist->tail = newnode;

    }else{

    newnode->next = plist->tail->next;

    plist->tail->next = newnode;

    }

    (plist->size)++;

}

int LFirst(List* plist,Ldata* data){

    if(plist->tail ==NULL) return 0;

    plist->cur = plist->tail->next; //첫번째

    plist->before = plist->tail; //끝

    *data = plist->cur->data;

    return 1;

}

int LNext(List* plist,Ldata* data){

    if(plist->tail ==NULL) return 0; //무한 반복 가능

    plist->before = plist->cur;

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

    *data = plist->cur->data;

    return 1;

}

Ldata LRemove(List* plist){

    Node* Rnode = plist->cur;

    Ldata Rdata = Rnode->data;

    if(Rnode == plist->tail){ //삭제 대상이 tail임

        if(plist->tail == plist->tail->next) // 노드가 1개일 경우

        {

            plist->tail = NULL;

        }else{

            plist->tail = plist->before; //그 외의 경우  

        }

    }

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

    plist->cur = plist->before;

    free(Rnode);

    (plist->size)--;

    return Rdata;

}

int Lcount(List* plist){

    return plist->size;

}

class CircularLinkedList<T> {

    private Node<T> tail = null;
    private Node<T> before =null;
    private Node<T> cur =null;
    private int size = 0;

    public void printAll(){

        if(tail == null){
            System.out.println("데이터 없음");
            return;
        }
        cur = tail.next;
        while(cur != tail){
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.print(cur.data+" "); //tail일때 하나 더 출력

    }
    public void insert(T data) {
        Node<T> newnode = new Node<>();
        newnode.data = data;

        if (this.tail == null) {
            this.tail = newnode;
            newnode.next = newnode;
        } else {
            newnode.next = tail.next; //기존 tail의 next
            tail.next = newnode; //기존 tail의 next를 newnode에 연결
            tail = newnode; // tail옮기기
        }
        size++;
    }

    public void insertFront(T data) { 
        Node<T> newnode = new Node<>();
        newnode.data = data;

        if (this.tail == null) {
            this.tail = newnode;
            newnode.next = newnode;
        } else {
            newnode.next = tail.next;
            tail.next = newnode;
        }
        size++;
    }
    //데이터를 앞에 추가하는 경우이다.
    // tail이 null일때 newnode, newnode.next=newnode인 것 빼곤 
    //기존 리스트에서 추가하는 것과 크게 다를바 없다.

    public T get(int index) {
        T error = (T) new Integer(Integer.MIN_VALUE); //임의로 지정
         cur = tail.next;
        if (tail == null) {
            System.out.print("조회할 데이터가 없습니다.");
            return error; //근데 자료형 여러가지니까 그냥 System.exit가 나을듯하다..
        } else if (index < 0 || index > size) {
            System.out.print("index 지정 오류");
            return error;
        } else {
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
        }
        return cur.data;
    }

   public T get() {
     return get(0);
    }

    public T Remove(int index){
         before = tail;
         cur = tail.next;
        Node<T> remove;
        T rdata;
       if(index <0 || index>size){
           System.out.print("인덱스 지정 오류");
           System.exit(-1);
       }else if(tail == null){
           System.out.print("저장된 데이터 없다");
           System.exit(-1);
       }
       //인덱스 찾기
       for(int i=0;i<size;i++){
           before = cur;
           cur = cur.next;
       }
        remove = cur;
        rdata = remove.data;

       if(cur == tail){ //인덱스가 끝을 가리킨다면
           if(tail == tail.next){ //하나 남음
               tail = null;
           }else{
               tail = before;
           }
       }
       before.next = cur.next;
       cur = before;
       size--;
       return rdata;
    }
    public T Remove(){
        return Remove(0);
    }

    public int size(){
        return size;
    }
        private class Node<T> {
            T data;
            Node next;
        }

}

자바 코드이다.

 

 

대부분 기존 연결리스트와 같다. Remove만 생각을 조금 해보자 

출처:https://www.geeksforgeeks.org/delete-a-linked-list-node-at-a-given-position/

 

데이터를 지우기 위해 cur가 before가 필요하다.

cur은 맨 앞을 가리킨다 == tail->next

before은 맨 끝을 가리키며, cur보다 왼쪽에 위치한다. == tail

 

1. 일반적인 데이터 지우기 

 

지우기를 원하는 노드와 값을 따로 저장한 뒤,

cur에 왼쪽에 있는 before의 next를 cur의 next에 연결해준다. 

cur을 before와 동일한 위치에 위치시킨다.

 

2. 예외상황

 

2.1 지우고자하는 노드와 값이 tail과 같을 때 

  -  tail을 before위치에 위치 시킨 후 삭제를 진행 

2.2 지우고자하는 노드와 값이 tail과 같으면서 데이터가 1개 밖에 없을 때

  - tail에 null을 집어넣는다.

 

 

참고자료 :윤성우 열혈자료구조 

https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks