4 minute read

1. 리스트

List(linear list) : 항목들이 순서(또는 위치)를 갖는 자료 구조

스택이나 큐에서는 자료의 접근이 전단이나 후단으로 제한되어 있지만, 리스트에서는 임의의 위치에 있는 항목에 접근할 수 있다

추상 자료형

데이터 : 임의의 접근 방법을 제공하는 같은 타입 요소들의 순서 있는 모임

연산 :
    - init() : initializing the list
    - insert(pos, item) : pos 위치에 새로은 요소 item을 삽입한다.
    - delete(pos) : pos 위치에 있는 요소를 삭제한다.
    - get_entry(pos) : pos 위치에 있는 요소를 반환한다.
    - is_empty() : 리스트가 비어있는지 검사한다.
    - if_full() : 리스트가 가득 차 있는지 검사한다.
    - find(item) : 리스트에 요소 item이 있는지 살핀다.
    - replace(pos, item) : pos 위치에 있는 요소를 새로운 요소 item으로 바꾼다.
    - size() : 리스트 안의 요소의 개수를 반환한다.

2. 리스트의 구현

배열로 구현한 list

배열을 이용하여 리스트를 구현하면 저장할 수 있는 요소 개수에 제한이 생기며, 큰 배열을 사용한다면 메모리의 낭비가 심하게 된다. 또한 삽입이나 삭제를 할 때 많은 항목들이 이동해야 한다.

// 리스트의 구조
typedef int Element;
Element data[MAX_LIST_SIZE]; // 정수의 일차원 배열과 배열의 크기ㅋ
int length = 0; // 현재 리스트에 저장된 요수의 개수

// 리스트의 연산
void init_list()            {length = 0;}
void clear_list()           {length = 0;}
int is_empty()              {return length == 0;}
int is_full()               {return length == MAX_LIST_SIZE;}
int get_entry(int id)       {return data[id];}
void replace(int id, Element e) {data[id] = e;}
int size()                  {return length;}
void insert(int pos, int e)
{
    int i;
    if (is_full() == 0 && pos >= 0 && pos <= length) {
        for (i = length; i > pos; i--)
            data[i] = data[i-1]; // 삽입하는 항목 이후의 항목들을 모두 한 칸씩 뒤로 이동시킨다.
        data[pos] = e; // pos 위치에 새로운 항목 e를 삽입한다.
        length++; // 리스트 요수의 개수를 1 증가시킨다.
    }
    else error("포화상태 오류 또는 삽입 위치 오류");
}
void delete(int pos)
{
    int i;
    if (is_empty() && 0 <= pos && pos < length) {
        for (i = pos + 1; i < length; i++>) {
            data[i - 1] = data[i]; // 삽입하는 항목 뒤에 있는 항목들을 모두 앞으로 한 칸씩 옮긴다.
            length--; // 요수의 개수를 1 감소시킨다.
        }
    }
    else error("공백상태 오류 또는 삭제 위치 오류");
}
int find(Element e)
{
    int i;
    for (i = 0; i < length; i++>)
        if (data[i] == e) return i; // 모든 항목에 대해 e와 같은지 비교하고, 같은 경우 그때의 인덱스 id를 반환한다.
    return -1; // 같은 항목이 없으면 -1을 반환한다.
}

연결 리스트로 구현된 list

연결 리스트는 물리적으로 흩어져 있는 자료들을 하나로 묶는 방법으로 동적으로 크기가 변할 수 있는 자료에 적합하다. 연결리스트를 이용해 리스트를 구현하면 배열로 구현할 때 생기는 문제를 해결할 수 있다.

연결 리스트는 노드로 구성되며, 각 노드는 항목의 자료를 저장하는 데어터 필드와 다음 노드를 가리키는 링크 필드로 구성된다.

  • Head pointer(헤드 포인터) : List의 시작을 나타내는 Node
#define Element int
typedef struct LinkedNode {
    Element data;               // data field
    struct LinkedNode* link     // link field
} Node;

Node* head;                     // 시작 node를 가리키기 위한 head pointer

void init_list()                {head = NULL;}
int is_empty()                  {return head == NULL;}
Node* get_entry(int pos)
{
    Node* p = head;
    int i;
    for (i = 0; i < pos; i++, p = p -> link)
        if (p == NULL) return NULL;
    return p;
}
int size()
{
    Node* p;
    int count = 0;
    for (p = head; p != NULL; p = p -> link)
        count++;
    return count;
}
void replace(int pos, Element e)
{
    Node* node = get_entry(pos);
    if (node != NULL)
        node -> data = e;
}
Node* find(Element e)
{
    Node* p;
    for (p = head; p != NULL; p = p -> link)
        if (p -> data == e) return p;
    return NULL;
}
void clear_list()
{
    while (is_empty() == 0)
        delete(0);
}
void insert_next(Node *before, Node *node)
{
    if (node != NULL) {
        node -> link = before -> link
        before -> link = node;
    }
}
void insert(int pos, Element e)
{
    Node *new_node, *prev;

    new_node = (Node*)malloc(sizeof(Node));
    new_node -> data = e;
    new_node -> link = NULL

    if (pos == 0) {
        new_node -> link = head;
        head = new_node;
    }
    else {
        prev = get_entry(pos - 1);
        if (prev != NULL)
            insert_next(prev, new_node);
        else free(new_node);
    }
}
Node* remove_next(Node *before)
{
    Node* removed = brefore -> link;
    if (removed != NULL)
        before -> link = removed -> link;
    return removed;
}
void delete(int pos)
{
    Node* prev, *removed;

    if (pos == 0 && is_empty() == 0) {
        removed = head;
        head = head -> link;
        free(removed);
    }
    else {
        prev = get_entry(pos - 1);
        if (prev != NULL) {
            removed = remove_next(prev);
            free(removed);
        }
    }
}

헤드 포인터와 헤드 노드

Head node : 포인터가 아닌 구조체를 시작 노드로 사용하며 link field만으로 구성된 노드

3. 다양한 형태의 연결 리스트

Circular linked list(원형 연결 리스트)

Circular linked list : 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 연결 리스트

리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적이다.

Doubly linked list(이중 연결 리스트)

Doubly linked list : 하나의 node가 선행 node와 후속 node에 대한 두 개의 link를 가지는 list

공간을 많이 차지하고 코드가 복잡하지만 다른 연결 리스트와 달리 양방향으로 자유롭게 움직일 수 있다.

typedef struct DbLinkedNode {
    Element data;                   // data field
    struct DblLinkedNode* prev;     // 선행 node
    struct DblLinkedNode* next;     // 후속 node next(not link)
} Node;

void insert_next(Node *before, Node *n)
{
    n -> prev = before;
    n -> next = brefore -> next;
    if (before -> ext != NULL) brefore -> next -> prev = n;
    before -> next = n;
}

void remove_curr(Node *n)
{
    if (n -> prev ! = NULL) n -> prev -> next = n -> next;
    if (n -> next ! = NULL) n -> next -> prev = n -> prev;
}

You may also enjoy