[Data Structure] List(리스트)

리스트는 다량의 데이터를 정리하기 위한 자료구조이다. 항목들이 차례대로 저장되어 있으며 이는 순서 또는 위치를 가진다.

추상자료형 리스트

• n개의 element형으로 구성된 순서 있는 모임

• 메서드는 insert(list, index, item), insert_last(list, item), insert_first(list, item), delete(list, index), get_entry(list, index), get_length(list)

• 배열로 구성하는 경우는 구현의 난이도가 쉽다는 장점이 있지만, 크기가 고정되며 새로운 데이터를 삽입하거나 삭제할 경우 기존의 데이터를 이동해야 한다는 담점이 있음

• 연결리스트로 구성하는 경우는 크기가 제한되지 않고 중간에 쉽게 삽입하거나 삭제할 수 있다는 장점이 있으나, 오류가 엄청나게 많이 발생함

배열로 구현한 리스트

• 순차적인 메모리 공간을 할당하므로 리스트의 순차적 표현

• insert(), delete()의 경우, 인덱스를 확인 후에 기존 데이터를 이동할 필요가 있음

  #include <stdio.h>
  #include <stdlib.h>
  
  #define MAX_SIZE 5
  
  typedef int element;
  
  typedef struct {
    int size;
    element array[MAX_SIZE];
  } ArrayList;
  
  void init_array(ArrayList *l) {
    l->size = 0;
  }
  
  int is_empty(ArrayList *l) {
    return l->size == 0;
  }
  
  int is_full(ArrayList *l) {
    return l->size == MAX_SIZE;
  }
  
  element get_entry(ArrayList *l, int idx) {
    if (idx < 0 || idx >= l->size) {
      printf("error\n");
      return 0;
    } else {
      return l->array[idx];
    }
  }
  
  void print_array(ArrayList *l) {
    for (int i = 0; i < l->size; i++) {
      printf("->%d", l->array[i]);
    }
    printf("\n");
  }
  
  void insert_last(ArrayList *l, int item) {
    if (l->size >= MAX_SIZE) {
      printf("리스트 범위 초과\n");
    } else {
      l->array[l->size++] = item;
    }
  }
  
  void insert(ArrayList *l, int index, element item) {
    if (!is_full(l) && (index >= 0) && (index <= l->size)) {
      for (int i = (l->size - 1); i >= index; i--) {
        l->array[i + 1] = l->array[i];
      }
      l->array[index] = item;
      l->size++;
    }
  }
  
  void clear(ArrayList *l){
    for (int i = l->size; i>-1; i--){
      l->array[i] = 0;
    }
    l->size = 0;
  }
  
  void replace(ArrayList *l, int index, int item){
    if (index < 0 || index > l->size){
      printf("유효 인덱스가 아닙니다.\n");
    } else{
      l->array[index] = item;
    }
  }
  
  element delete (ArrayList *l, int index) {
    if (index < 0 || index >= l->size) {
      printf("유효한 인덱스 아닙니다.\n");
      return 0;
    } else {
      element item;
      item = l->array[index];
      for (int i = index; i < l->size - 1; i++) {
        l->array[i] = l->array[i + 1];
      }
      l->size--;
      return item;
    }
  }
  
  int get_length(ArrayList *l){
    return l->size;
  }
  
  int main(void) {
    ArrayList list;
    init_array(&list);
    insert(&list, 0, 10);
    print_array(&list);
    insert(&list, 0, 20);
    print_array(&list);
    insert(&list, 0, 30);
    print_array(&list);
    insert(&list, 0, 40);
    print_array(&list);
    insert_last(&list, 70);
    print_array(&list);
    delete(&list, 0);
    print_array(&list);
    printf("%d\n", get_length(&list));
    replace(&list, 4, 90);
    print_array(&list);
    replace(&list, 0, 50);
    print_array(&list);
  
    delete(&list, 2);
    print_array(&list);
  
  
    return 0;
  }
  
  

연결 리스트

• 동적으로 크기가 변할 수 있으며, 삭제나 삽입 시에 데이터를 이동할 필요가 없는 리스트

• 노드는 데이터 필드와 링크 필드로 나뉘어짐

• 데이터 필드는 저장해야 하는 데이터, 링크 필드는 다른 노드를 가리키는 포인터가 저장

• 이때 링크 필드는 자기 자신을 참조하는 포인터를 포함하는 구조체인 자기참조구조체의 형태로 관리

• 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수 - 헤드 포인터

• 마지막 노드의 링크 필드는 연결된 것이 없으므로 NULL로 설정

  #include <stdio.h>
  #include <stdlib.h>
  
  typedef struct ListNode{
    int data;
    struct ListNode *link;
  } ListNode;
  
  ListNode* insert_first(ListNode *head, int item){
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->data=item;
    p->link=head;
    head = p;
    return head;
  }
  
  ListNode* insert(ListNode *head, ListNode *pre, int value){
    ListNode *p = (ListNode *)malloc(sizeof(ListNode));
    p->data = value;
    p->link = pre->link;
    pre->link = p;
    return head;
  }
  
  ListNode* delete_first(ListNode *head){
    ListNode *removed;
    if (head == NULL) return NULL;
    removed = head;
    head = removed->link;
    free(removed);
    return head;
  }
  
  ListNode* delete(ListNode *head, ListNode *pre){
    ListNode *removed;
    removed = pre->link;
    pre->link = removed->link;
    free(removed);
    return head;
  }
  
  void print_list(ListNode *head){
    for (ListNode *p = head; p!=NULL; p = p->link){
      printf("%d->", p->data);
    }
    printf("NULL \n");
  }
  
  int get_entry(ListNode *head, int index){
    if (index < 0)
      return -1;
    ListNode *tmp;
    tmp = head;
    for (int i = 0; i < index && tmp != NULL; i++){
      tmp = tmp->link;
    }
    return tmp->data;
  }
  
  int get_length(ListNode *head){
    ListNode *tmp;
    int length = 0;
    tmp = head;
    if (head == NULL){
      return length;
    }
  
    for (int i = 0;  tmp != NULL; i++){
      length += 1;
      tmp = tmp->link;
  
    }
    return length;
  }
  
  int find_value(ListNode *head, int value){
    ListNode *tmp = head;
    for (int i = 0; tmp != NULL; i++){
      if (tmp -> data == value){
        return i;
      }
      tmp = tmp -> link;
  
    }
    return -1;
  }
  
  ListNode* reverse(ListNode *head){
    ListNode *p, *q, *r;
    p = head;
    q = NULL;
    while (p!=NULL){
      r = q;
      q = p;
      p = p->link;
      q -> link= r;
    }
    return q;
  }
  
  int main(){
    ListNode *head = NULL;
  
    for (int i=0 ; i<10; i++){
      head = insert_first(head, i);
      print_list(head);
    }
    printf("%d\n", find_value(head, 8));
    printf("%d\n", get_entry(head, 0));
    printf("%d\n", get_length(head));
    printf("%d\n", get_entry(head, 9));
  
    head = reverse(head);
    print_list(head);
    for (int i = 0; i<10; i++){
      head = delete_first(head);
      print_list(head);
    }
  }