[자료구조] 원형리스트와 연결리스트 개념과 구조, 구현과 활용

단순 연결 리스트

가장 첫 노드는 head를 가리킴
마지막 노드의 링크는 NULL로 표시
끝 노드를 찾는 시간 복잡도: O(n)

원형 연결 리스트

마지막 노드의 링크가 첫 번째 노드를 가리킴
하나의 노드에서 링크를 따라가면 모든 노드 방문 가능
모든 노드의 링크가 NULL이 아니다.(head가 NULL인 경우 제외)

변형된 원형 연결 리스트

head 포인터 하나로 리스트의 처음과 끝을 가장 효율적으로 표현(찾는다)
- 마지막 노드 : head가 가리킴
- 첫 번째 노드 : head → link가 가리킴
- cf) 노드가 1개일 때 : head → link가 가리키는 게 head

가장 처음에 노드 삽입하는 경우

원형 연결 리스트가 NULL(노드 0개) 일 경우
- head = node;
  - head를 NULL에서 새로운 노드로 설정(끝 노드로 설정)
- head → link = head;
  - 노드가 1개이기 때문에 첫 노드와 마지막노드가 같다. 따라서 head == head→link
원형 연결 리스트의 노드가 1개 이상인 경우

node → link = head → link
- 새로운 노드가 첫 노드(head → link)를 가리키게 함.
head → link = node;
- 첫 노드(head → link)를 새로운 노드로 설정

가장 끝에 노드를 삽입하는 경우

원형 연결 리스트가 NULL(노드 0개) 일 경우
- 가장 처음에 노드를 삽입하는 경우와 같음(노드가 0개 일 때)
원형 연결 리스트의 노드가 1개 이상인 경우

node → link = head → link;
- 가장 끝에 노드를 삽입했으므로 Node가 head역할을 해야 한다.
  → 그러므로 node → link는 첫 노드인 head → link를 가리켜야 한다.
head → link = node;
- 기존에 있던 head는 일반적인 node가 됐기 때문에 새로운 head인 node를 가리켜야 한다.
  → 즉 head → link는 node를 가리켜야 한다.
head = node;
- 공식적으로 변수 head를 node로 변경한다.

원형 연결 리스트 가장 첫 노드 삭제

노드가 0개인 경우
- 불가능
노드가 1개인 경우
1. head = NULL;
  - 끝 노드 NULL 처리
2. head → link = NULL;
  - 첫 노드 NULL 처리
3. free(head);
  - 메모리 낭비를 막기 위해 사용하지 않는 노드(head) 메모리 할당 해제
노드가 2개 이상인 경우
1. ListNode* ptr = head -> link;
  - 맨 처음 노드를 나타내는 ptr 노드를 만듦
2. head -> link = ptr -> link;
  - 마지막 노드가 가리키는 노드를 첫 노드의 링크(두 번째 노드)로 설정
  1. free(ptr);
- 필요 없는 노드 메모리할당 해제
1. return head;
  - 새로운 head 노드 반환

원형 연결 리스트 가장 끝 노드 삭제

노드가 0개인 경우
- 불가능
노드가 1개인 경우
- 원형리스트 첫 노드를 1개를 삭제할 때와 같음
노드가 2개 이상인 경우

ListNode* pre = head; // head 이전의 노드 담을 예정
ListNode* ptr = head; // head 노드

// pre 노드를 pre 노드의 다음 노드(링크)로 변경하는 과정을 반복
// 이 반복을 해당 노드의 다음 노드가 head가 될때까지 반복한다.
do{
    pre = pre -> link;
}while(pre -> link != ptr);

//새로 head가 될 pre의 다음 링크를 첫번째 노드로 설정
pre -> link = head -> link;
head = pre; // head를 pre로 설정
free(ptr); // 삭제한 노드의 메모리를 삭제
return head; // 계산한 head 노드를 반환

변형된 원형 연결리스트 구현

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

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

// 원형 리스트 순서대로 출력
void print_list(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;
        head -> 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;
        head -> link = head;
    }
    else{
        node -> link = head -> link;
        head -> link = node;
        head = node;
    }
    return head;
}

// 원형 리스트 처음 노드 삭제
ListNode* delete_first(ListNode*head){
    if(head == NULL) return head;
    else if(head -> link == head){
        head = NULL;
        head -> link = NULL;
        return head;
    }
    ListNode* ptr = head -> link;
    head -> link = ptr -> link;
    free(ptr);
    return head;
}

//원형 리스트 마지막 노드 삭제
ListNode* delete_last(ListNode* head){
    if(head == NULL) return head;
    else if(head -> link == head){
        head = NULL;
        head -> link = NULL;
        free(head);
        return head;
    }
        ListNode* pre = head;
    ListNode* ptr = head;
    do{
        pre = pre -> link;
    }while(pre -> link != ptr);
    pre -> link = head -> link;
    head = pre;
    free(ptr);
    return head;
}

// 원형 리스트 노드 개수 반환
int get_Length(ListNode* head){
    if(head == NULL) return 0;
    ListNode* p;
    p = head;
    int count = 0;
    do{ 
        p = p -> link;
        count++;
    }
    while(p != head);
    return count;
}
int main(){
    ListNode* head = NULL;
    head = insert_first(head,1); print_list(head);
    head = insert_first(head,2); print_list(head);
    head = insert_first(head,3); print_list(head);
    head = insert_first(head,4); print_list(head);
    head = delete_first(head); print_list(head);
    head = delete_last(head); print_list(head);
    head = delete_last(head); print_list(head);

}

<출력>

**1 -> 
2 ->1 -> 
3 ->2 ->1 -> 
4 ->3 ->2 ->1 -> 
3 ->2 ->1 -> 
3 ->2 -> 
3 ->**

이중 연결 리스트

단순 연결리스트 단점 : 선행 노드를 바로 찾기 어렵다. → 위 문제를 해결하는 자료구조
장점 : 특정 노드에서 양방향으로 자유롭게 움직일 수 있음
단점 : 공간을 많이 차지
- 노드는 3개의 필드로 이루어짐
  - 왼쪽 링크 필드, 데이터 필드. 오른쪽 링크 필드
- head 포인터를 사용하지 않고 head node라는 특별한 노드를 사용
  → 삽입, 삭제를 간편하게 하기 위해
  - 헤드노드
    - 공백 리스트에서부터 기본적 존재
    - 데이터 필드에는 아무런 정보도 없음
    - 공백 리스트의 헤드 노드의 조건
      - p == p→llink && p == p→ rlink(True)

삽입 연산

before 다음에 새 노드를 삽입하는 순서

newNode → llink = before;
- 새 노드의 왼쪽 링크를 before노드로 설정
newNode → rlink = before → rlink;
- 새 노드의 오른쪽 링크를 before 노드의 오른쪽 링크였던 노드로 설정
before → rlink → link = newNode;
- before 노드의 오른쪽 링크였던 노드의 왼쪽 링크를 새로운 노드로 설정
before → rlink = newNode;
1. before 노드의 오른쪽 링크를 newNode로 설정

삭제 연산

removed로 지정된 노드를 삭제하는 순서

removed → llink → rlink = removed → rlink;
- removed노드의 왼쪽 링크 즉, 왼쪽 노드의 rlink(다음 노드)를 removed → rlink
  그러니까 removed의 다음 노드로 설정
removed →rlink → llink = removed → llink;
- removed의 다음 노드의 왼쪽 링크 그러니까 이전 노드를 removed의 이전노드로 설정

이중 연결 리스트 코드 구현

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

typedef int element;

// 노드 구조체 정의
typedef struct DListNode{
    element data;
    struct DListNode *llink;
    struct DListNode *rlink;
}DListNode;

// 노드 초기화
void init(DListNode* phead){
    phead -> llink = phead;
    phead -> rlink = phead;
}
// 노드 전체 출력 함수
void print_list(DListNode* phead){
    DListNode *p;
    for(p = phead -> rlink; p !=phead; p = p ->rlink){
        printf("<-||%d||->",p->data);
    }
    printf("\n");
}

// before 노드 뒤에 데이터 노드 삽입
void dinsert(DListNode* before, element data){

    DListNode* newnode = (DListNode*)malloc(sizeof(DListNode));
    newnode -> data = data;
    newnode -> llink = before;
    newnode -> rlink = before->rlink;
    before -> rlink = newnode;
    before -> rlink -> llink = newnode;
}

// 노드에서 삭제할 노드(removed)를 골라 삭제
void ddelete(DListNode* head, DListNode* removed){
    if(removed == head)return;
    removed -> llink -> rlink = removed -> rlink;
    removed -> rlink-> llink = removed -> llink;
    free(removed);
}

int main(){
    DListNode* head = (DListNode*)malloc(sizeof(DListNode));
    init(head);
    printf("삽입단계 \n");
    for(int i = 0; i < 5; i++){
        dinsert(head,i);
        print_list(head);
    }
    printf("삭제 단계 \n");
    for(int i = 0; i < 5; i++){
        print_list(head);
        ddelete(head,head->rlink);
    }
    free(head);
    return 0;
}

<출력>

삽입단계
<-||0||->
<-||1||-><-||0||->
<-||2||-><-||1||-><-||0||->
<-||3||-><-||2||-><-||1||-><-||0||->
<-||4||-><-||3||-><-||2||-><-||1||-><-||0||->
삭제 단계 
<-||4||-><-||3||-><-||2||-><-||1||-><-||0||->

<추가 구현 — 이중 연결 리스트 검색 구현>

// ~~~~~~~~~~~~  위의 연결 리스트 구현 함수 코드 ~~~~~~~~~ //
DListNode *search(DListNode *L, element data){
  DListNode *p;
  p = L -> rlink;
  do{
      if(p -> data == data) return p;
      p = p->rlink;
  }while(p != L);

  return NULL;
}

int main(){
  DListNode* head = (DListNode*)malloc(sizeof(DListNode));
  init(head);
  int num;
  printf("데이터의 개수를 입력하시오 : ");
  scanf("%d",&num);
  printf("\n");

  for(int i = 1; i <= num; i++){
      int val;
      printf("노드 %d의 데이터를 입력하시오:",i);
      scanf("%d",&val);
      printf("\n");
      dinsert(head,val);
  }
  DListNode* find = search(head,3);
  if(find == NULL) printf("값이 없습니다");
  else printf("%d",find->data);
}

<출력>

데이터의 개수를 입력하시오 : 3

노드 1의 데이터를 입력하시오:3

노드 2의 데이터를 입력하시오:6

노드 3의 데이터를 입력하시오:9

3

이중 연결 리스트 활용 - Mp3 플레이어

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

typedef char element[100];
typedef struct DListNode {    // 이중연결 노드 타입
    element data;
    struct DListNode* llink;
    struct DListNode* rlink;
} DListNode;

DListNode* current;

// 이중 연결 리스트를 초기화
void init(DListNode* phead)
{
    phead->llink = phead;
    phead->rlink = phead;
}

// 이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead)
{
    DListNode* 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 dinsert(DListNode *before, element data)
{
    DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
    strcpy(newnode->data, data);
    newnode->llink = before;
    newnode->rlink = before->rlink;
    before->rlink->llink = newnode;
    before->rlink = newnode;
}

// 노드 removed를 삭제
void ddelete(DListNode* head, DListNode* removed)
{
    if (removed == head) return;
    removed->llink->rlink = removed->rlink;
    removed->rlink->llink = removed->llink;
    free(removed);
}

int main(){
    char ch;
    DListNode* head = (DListNode*)malloc(sizeof(DListNode));
    init(head);

    dinsert(head,"A");
    dinsert(head,"B");
    dinsert(head,"C");

    current = head ->rlink;
    print_dlist(head);
    do{
        printf("\n명령어 입력(<, >, q): ");
        ch = getchar();
        if(ch == '<'){
            current = current -> llink;
            // head노드는 아무런 값이 없으므로 바로 nextnode
            if(current == head) current = current -> llink;
        }
        else if(ch == '>'){
            current = current -> rlink;
            if(current == head) current = current -> rlink;
        }
        print_dlist(head);
        getchar();
    }while(ch != 'q');
    free(head);
}

<출력>

<-| #C# |-> <-| B |-> <-| A |-> 

명령어 입력(<, >, q): >
<-| C |-> <-| #B# |-> <-| A |-> 

명령어 입력(<, >, q): >
<-| C |-> <-| B |-> <-| #A# |-> 

명령어 입력(<, >, q): >
<-| #C# |-> <-| B |-> <-| A |-> 

명령어 입력(<, >, q): <
<-| C |-> <-| B |-> <-| #A# |-> 

명령어 입력(<, >, q): <
<-| C |-> <-| #B# |-> <-| A |-> 

명령어 입력(<, >, q): q
<-| C |-> <-| #B# |-> <-| A |->

저작자표시 변경금지

Today :

단순 연결 리스트

원형 연결 리스트

변형된 원형 연결 리스트

가장 처음에 노드 삽입하는 경우

가장 끝에 노드를 삽입하는 경우

원형 연결 리스트 가장 첫 노드 삭제

원형 연결 리스트 가장 끝 노드 삭제

변형된 원형 연결리스트 구현

이중 연결 리스트

삽입 연산

삭제 연산

이중 연결 리스트 코드 구현

<추가 구현 — 이중 연결 리스트 검색 구현>

이중 연결 리스트 활용 - Mp3 플레이어

티스토리툴바

단순 연결 리스트

원형 연결 리스트

변형된 원형 연결 리스트

가장 처음에 노드 삽입하는 경우

가장 끝에 노드를 삽입하는 경우

원형 연결 리스트 가장 첫 노드 삭제

원형 연결 리스트 가장 끝 노드 삭제

변형된 원형 연결리스트 구현

이중 연결 리스트

삽입 연산

삭제 연산

이중 연결 리스트 코드 구현

<추가 구현 — 이중 연결 리스트 검색 구현>

이중 연결 리스트 활용 - Mp3 플레이어

검색 태그

티스토리툴바