연결 리스트(Linked List)

안녕하세요!

이번 주에는 좀 글을 많이 쓰는 듯하네요 ㅎ

그래도 많이 쓰는것을 보니 계획대로 살고 있는 것 같아서 뿌듯하네요 :)

(하지만 아직 할것이 산덤이라는것이 함정...)

---

목차

1. List에 대한 설명
2. List의 추상 데이터 타입 정의
3. List 실제 구현

---

이번시간에는 연결 리스트에 대해서 알아볼 거예요

연결 리스트 또는 LinkedList라고 부르는 이것은 리스트인데 연결로 이루어져 있는 리스트라는 것인데

먼저 리스트란 - 항목들이 차례대로 정의되어 있고 이것들은 순서와 위치를 가지는 것이 특징입니다

자바를 하실 줄 아시는 분들은 아실 텐데

자바에 보시면 ArrayList와 LinkedList가 있는 것을 확일 할 수 있는데

ArrayList는 리스트인데 배열로 구현한 리스트이고

LinkedList는 리스트인데 연결로 구현한 리스트라고 볼 수 있습니다

연결로 이루어져 있다는 말은 C언어로 표현하자면 포인터로 이루어져 있다고 볼 수 있습니다

<그림>

 

배열로 구성된 리스트

• 단점: 배열의 크기가 정적이기 때문에 자칫하면 메모리를 비효율적으로 쓸 수도 있다는 것
• 장점: 구현이 쉽다는 것입니다

연결로 구성된 리스트

• 단점: 배열에 비해서 구현하기가 어렵습니다... (왜냐하면 포인터를 사용하기 때문이죠..ㄷㄷ)
• 장점: 배열보다는 메모리를 더 알맞게 사용할 수 있습니다

이번에는 배열로 구현하는 것은 쉬우니깐 링크로 구성하는 법만 알아보도록 할게요 ㅎ (귀찮은 건 절대 아닙니다 ㅎㅎ)

---

LinkedList의 추상 데이터 타입 구현

• insert(list, pos, item) -> pos위치에다가 요소를 추가하는 함수
• insert_last(list, item) -> 맨 끝에 요소를 추가하는 함수
• insert_firts(list, item) -> 맨 처음에 요소를 추가하는 함수
• delete(list, pos) -> pos위치의 요소를 제거하는 함수
• get_length(list) -> 리스트의 길이를 구현하는 함수
• is_empty(list) -> 리스트가 비었는지 확인한다

---

LinkedList의 코드로 구현

작성 언어 : C언어

 

typedef int element;

typedef struct LinkedList {
    element data;
    struct LinkedList *link;
}LinkedList;

typedef struct HeaderLink {
    int size;
    LinkedList *first;
    LinkedList *last;
}headerLink;

headerLink *create() {
    headerLink * header = (headerLink *)malloc(sizeof(headerLink));
    header->size = 0;
    header->first = NULL;
    header->last = NULL;
    
    return header;
}

 

int is_empty(LinkedList *head){
    return (head == NULL);
}

void error(char *message){
    fprintf(stderr, "%s", message);
    exit(1);
}

 

void insert(headerLink *head, LinkedList *pre, element value){
    
    LinkedList *p = (LinkedList *)malloc(sizeof(LinkedList));
    p->data = value;
    p->link = NULL;
    if(head->first == NULL){
        head->first = p;
        head->last = p;
    }else{
        p->link = pre->link;
        pre->link = p;
    }
    head->size += 1;
}

void insert_first(headerLink *head, element value){
    
    LinkedList *p = (LinkedList *)malloc(sizeof(LinkedList));
    p->data = value;
    p->link = NULL;
    if(head->first == NULL){
        head->first = p;
        head->last = p;
    }else{
        p->link = head->first;
        head->first = p;
    }
    head->size += 1;
}

void insert_last(headerLink *head, element value) {
    LinkedList *p = (LinkedList *)malloc(sizeof(LinkedList));
    p->data = value;
    p->link = NULL;
    if(head->last == NULL){
        head->first = p;
        head->last = p;
    }else {
        head->last->link = p;
        head->last = p;
    }
    head->size += 1;
}

 

void delete(headerLink *head, LinkedList *pre){
    LinkedList *removed = pre->link;
    pre->link = removed->link;
    free(removed);
    head->size -= 1;
}

int get_length(headerLink *head) {
    return head->size;
}

여기서는 Link로 구현한 리스트는 head노드에 처음 노드와 끝 노드와 리스트의 사이즈를 저장하는 공간을 만들어서

나중에 시간 복잡도 O(1)로 끝 노드에 데이터를 추가할 수 있게 도와준다

아직 위에 코드는 index번호를 가지고 있지 않아서 insert 하는 함수가 조금 어색하긴 한데

LinkedList 구조체에 index번호를 가질 수 있는 공간을 하나 만들어주면 가능할 것 같다

대신에 insert함수를 사용할 때는 O(N)의 시간 복잡도는 피할 수 없을 듯하다

---

이번에 LinkedList를 구현하면서 느낀 점은 java나 c++개발자들에게 굉장히 고마워해야겠다는 생각이 드네요 ㅎㅎ

포인터를 사용해서 그런지 익숙하지 않으면 짜고 이해하기가 쉽지 않을 듯하네요..ㄷㄷ

오늘은 여기까지 입니다!! 읽어주셔서 감사합니다!!

궁금하신 점이나 부족한 점은 밑에 댓글로 남겨주세요!!