연결 리스트 2

7장 연결 리스트 2

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

원형 연결 리스트

• 원형 연결 리스트란?

  마지막 노드가 첫 번째 노드를 가리키는 리스트 즉, 마지막 노드의 링크 필드가 NULL이 아니라 첫 번째 노드 주소가 되는 리스트

• 장점 : 원형 연결 리스트에서는 하나의 노드에서 다른 모든 노드로의 접근이 가능하다.

  하나의 노드에서 링크를 계속 따라 가면 결국 모든 노드를 거쳐서 자기 자신으로 되돌아 올 수 있는 것.

  따라서 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이

원형 연결 리스트 구현

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

typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode *link;
} ListNode;

//출력
void print(ListNode* head)
{
    ListNode* p;

    if (head == NULL)
        return;
    
    p = head->link;
    do{
        printf("%d->", p->data);
        p = p->link;
    }while (p != head);

    printf("%d->", p->data);
}

//헤드에 삽입
ListNode* insert_first(ListNode* head, element data)
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    if (head == NULL) {
        head = node;
        node->link = head;
    }
    else {
        node->link = head->link;
        head->link = node;
    }
    return head;
}

ListNode* insert_last(ListNode*head, element data)
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    if (head == NULL){
        head = node;
        node->link = head;
    }
    else{
        node->link = head->link;
        head->link = node;
        head = node;
    }
    return head;
}

---

이중 연결 리스트

단순 연결 리스트 : 선행 노드 찾기 매우 어렵다 원형 연결 리스트 : 거의 전체 노드를 거쳐서 돌아와야함

이중 연결 리스트로 해결

• 특정 노드에서 양방향으로 자유롭게 움직일 필요가 있을 때 사용

핵심

p = p->llink->rlink = p->rlink->llink

노드의 구성

typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode* llink;
    struct ListNode* rlink;
} ListNode;

이중 연결 리스트 구현

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

typedef char element[100];
typedef struct ListNode{
    element data;
    struct ListNode* llink;
    struct ListNode* rlink;
} ListNode;

ListNode* current;

//초기화
void init(ListNode* phead)
{
    phead->llink = phead;
    phead->rlink = phead;
}

//출력
void print(ListNode* phead)
{
    ListNdoe* p;
    for (p = phead->rlink; p != phead; p = p->rlink){
        if (p == current)
            printf("<-| %s |-> ", p->data);
        else
            printf("<-| %s |-> ", p->data);
    }
    printf("\n");
}

//새 노드를 before의 오른쪽에 삽입.
void insert(ListNode *before, element data)
{
    ListNode *newnode = (ListNode *)malloc(sizeof(ListNode));
    strcpy(newnode->data, data);
    newnode->llink = before;
    newnode->rlink = before->rlink;
    before->rlink->llink = newnode;
    before->rlink = newnode;
}

//삭제
void delete(ListNode* head, ListNode* removed)
{
    if (removed == head)
        return;
    
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}