CS/자료구조

Ch05. 연결리스트-3

박 성 하 2022. 4. 7. 14:15
728x90

05-1. 원형 연결 리스트(Circular Linked List)

원형 연결 리스트의 이해

원형 연결 리스트 : 연결의 형태가 원을 이루는 구조의 연결 리스트

  • 머리에 노드 추가
  • 꼬리에 노드 추가
    머리와 꼬리의 구분이 없다
    하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다

변형된 원형 연결 리스트

하나의 포인터 변수가 머리가 아닌 꼬리를 가리킨다

  • 꼬리를 가리키는 포인터 변수 : tail
  • 머리를 가리키는 포인터 변수 : tail->next

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

  • LNext함수는 무한 반복 호출이 가능하고, 리스트 끝에 도달할 경우 첫 번째 노드부터 다시 조회
  • 정렬과 관련이 있던 기능은 제거
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE 1
#define FALSE 0

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 LInsetFront(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

-입력

void LInsert(List *plist, Data data); // 꼬리에 노드를 추가
void LInsertFront(List *plist, Data data); // 머리에 노드를 추가

변형된 원형 연결 리스트의 초기화와 노드의 삽입

리스트의 멤버를 NULL 또는 0으로 초기화

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

tail이 NULL을 가리킨다는 것은 노드가 하나도 추가되지 않았음을 의미

tail은 새 노드를 가리켜야 하고 새 노드도 자기자신을 가리켜야 한다
처음 추가된 노드는 그 자체로 머리이자 꼬리이다

void LInsert~(List *plist, Data data)   //꼬리에 노드를 추가
{
    Node *newNode = (Node*)malloc(sizeof(Node));    // 새 노드 생성
    newNode->data = data;   //새 노드에 데이터 저장

    if(plist->tail == NULL) // 첫 번째 노드라면,
    {
        plist->tail = newNode;  // tail이 새 노드를 가리키게 한다
        newNode->next = newNode // 새 노드 자신을 가리키게 한다.

    }
    else
    {
        ...차이가 나는 부분...
    }

    (plist->numOfData)++;
}
  • 머리에 노드를 추가
    )
  • void LInsetFront(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; // 새 노드와 4가 저장된 노드 연결 plist->tail->next = newNode; // 2가 저장된 노드와 새 노드 연결 } (plist->numOfData)++; }
  • 꼬리에 노드를 추가

노드를 꼬리에 추가했을 때와 머리에 추가했을 때의 유일한 차이점은 tail이 가리키는 노드가 다르다는 점이다

void LInsert(List *plist, Data data)   //꼬리에 노드를 추가
{
    Node *newNode = (Node*)malloc(sizeof(Node));    // 새 노드 생성
    newNode->data = data;   //새 노드에 데이터 저장

    if(plist->tail == NULL) // 첫 번째 노드라면,
    {
        plist->tail = newNode;  // tail이 새 노드를 가리키게 한다
        newNode->next = newNode // 새 노드 자신을 가리키게 한다.

    }
    else
    {
        newNode->next = plist->tail->next;
        plist->tail->next = newNode;
        plist->tail = newNode;  //LInsetFront함수와의 유일한 차이점
    }

    (plist->numOfData)++;
}

변형된 원형 연결 리스트의 데이터 조회

before는 cur보다 하나 앞선 노드를 가리켜야 한다

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

    plist->before = plist->tail // before가 꼬리를 가리키게 한다
    plist->cur = plist->tail->next; // cur이 머리를 가리키게 한다

    *pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

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

    plist->before = plist->cur; // before가 다음 노드를 가리키게 한다
    plist->cur = plist->cur->next;  // cur이 다음 노드를 가리키게 한다

    *pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 반환
    return TRUE;
}

리스트의 끝을 검사하는 코드가 존재하지 않는다
무한 반복 호출이 가능하다

변형된 원형 연결 리스트의 데이터 삭제

  1. 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 한다
  2. 포인터 변수 cur을 한 칸 뒤로 이동한다
Data LRemove(List *plist)
{
    Node *rpos = plist->cur;
    LData data = rpos->data;

    plist->before->next = cur->next;    // 핵심연산 1
    plist->cur = plist->before; // 핵심연산 2

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

더미 노드가 원형 연결리스트에는 존재하지 않는다

05-3. 양방향 연결 리스트

양방향 연결 리스트(이중 연결 리스트) : 노드가 양쪽 방향으로 연결된 구조

  • 구조체
  • typedef struct _node { Data data; //typedef int Data struct _node * next; // 오른쪽 노드를 가리키는 포인터 변수 struct _node * prev; // 왼쪽 노드를 가리키는 포인터 변수 }Node;
  • 더미 노드 양방향 연결 리스트
  • 원형 연결 기반의 양방향 연결 리스트

양방향 연결리스트 구현을 위한 헤더파일

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE    1
#define FALSE   0

typedef int Data;

typedef struct _node
{
    Data data;  //typedef int Data
    struct _node * next;    // 오른쪽 노드를 가리키는 포인터 변수
    struct _node * prev;    // 왼쪽 노드를 가리키는 포인터 변수
}Node;

typedef struct _DLinkedList
{
    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

양방향 연결 리스트의 초기화와 노드의 삽입

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)++;
}
newNode->next = plist->head; // 새 노드가 기존 노드를 가리키게 한다.
plist->head->prev = newNode; // 기존 노드가 새 노드를 가리키게 한다.

newNode->prev = NULL; // 새 노드의 prev에 NULL 저장
plist->head = newNode; // 포인터 변수 head가 새 노드를 가리키게 한다.

양방향 연결 리스트의 데이터 조회

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

    plist->cur = plist->head;   // cur이 첫 번째 노드를 가리키게 함
    *pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 반환
    return TRUE;
}
int LNext(List *plist, Data *pdata)
{
    if(plist->cur->next == NULL)
    {
        return FALSE;
    }

    plist->cur = plist->cur->next;  //cur을 오른쪽으로 이동
    *pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 반환
    return TRUE;
}
int LNext(List *plist, Data *pdata)
{
    if(plist->cur->next == NULL)
    {
        return FALSE;
    }

    plist->cur = plist->cur->next;  //cur을 오른쪽으로 이동
    *pdata = plist->cur->data;  // cur이 가리키는 노드의 데이터 반환
    return TRUE;
}
int LPrevious(List *plist, Data *pdata)
{
    if(plist->cur->prev == NULL)
    {
        return FALSE;
    }

    plist->cur = plist->cur->prev;  //cur을 왼쪽으로 이동
    *pdata = plist->cur->data;  //cur이 가리키는 노드의 데이터 반환
    return TRUE;
}
728x90
저작자표시 비영리

'CS > 자료구조' 카테고리의 다른 글

Ch07. 큐(Queue)  (0) 2022.04.07
Ch06. 스택(Stack)  (0) 2022.04.07
Ch04. 연결리스트-2  (0) 2022.04.07
Ch03. 연결리스트-1  (0) 2022.04.07
Ch02. 재귀  (0) 2022.04.07

'CS/자료구조'의 다른글

  • 현재글Ch05. 연결리스트-3

관련글

댓글

티스토리툴바