리스트

1. 리스트란?

• 리스트(list) 또는 선형 리스트(linear list)는 우리들이 자료를 정리하는 방법 중의 하나이다.

  L = (item(0), item(1), item(2), ... , item(n-1)) //이렇게 리스트를 표기할 수 있다.

• 리스트는 스택, 큐, 덱과 같이 항목들이 항목들이 일렬로 순서대로 들어 있는 선형 자료구조이다.

2. 리스트와 스택, 큐의 차이점

• 리스트는 스택, 큐가 front, rear로 자료의 접근이 제한되어 있었던 것과 다르게 임의의 위치에서도 접근이 가능하다.
• 이렇게 자유롭게 접근할 수 있으나, 그만큼 고려해야 할 점들이 많다.

3. 리스트의 연산

1) 공백상태와 포화상태 검사

• 공백상태는 length가 0인지를 검사하고, 포화상태는 length가 MAX_LIST_SIZE인지 검사하면 된다.

2) 단순한 연산들

• 리스트의 초기화 연산 init_list()에서는 length를 0으로 설정하면 되고, 리스트의 항목 수를 반환하는 size()에서는 length를 반환하면 된다.
• id번째 항목을 반환하는 연산 get_entry(id)는 data[id]이므로 이를 반환하면 되고, id번째 항목을 e로 교체하는 연산 replace(id, e)는 단순히 항목e를 data[id]에 복사(data[id]<-e)면 된다.
• 배열을 이용한 리스트를 비우는 연산 clear_list()는 리스트의 초기화와 같이 length를 0으로 설정하면 된다.

3) 리스트의 삽입 연산

void insert(int pos, int e){//리스트의 삽입연산
  if(is_full()==0 && pos >=0&& pos<=length){//pos=삽입위치, is_full = 꽉차있는지 확인
    for(int i=length;i>pos;i--)
      data[i]=data[i-1];//data를 삽입하고 밀어내기
    data[pos] = e;// 삽입할 값을 pos에 집어넣기
    length++;//리스트를 삽입할 때 length를 증가시켜 크기가 꽉차지 않게 함.
  }
  else error("포화상태 오류 또는 삽입 위치 오류");
}

4) 리스트의삭제 연산

void delete(int pos){//리스트의 삭제 연산
  if(is_empty()==0 && 0<=pos && pos<length){//is_empty() = 리스트가 비어있는지 확인, pos = 새로운 값을 삽입하는 위치
    for(int i=pos+1;i<length;i++){
        data[i-1] = data[i];//뒤에있는 항목들을 앞으로 당겨줌
      length--;//삭제가 끝나면 길이를 하나 줄여줌.
    }
  }
  else error("공백상태 오류 또는 삭제 위치 오류");
}

5) 리스트의 탐색 연산

int find(Element e){//리스트의 탐색연산
  for(int i = 0;i<length;i++)
    if(data[i]==e)//찾으려고 하는 값 e를 찾으면 그때의 인덱스 id를 반환.
      return i;
    return -1;//같은 항목이 없으면 -1을 반환
}

6) 리스트의 추상 자료형

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){//id위치에 있는 data를 반환
  return data[id];
}
int replace(int id,Element e){//id위치에 있는 data를 e로 교체
  data[id] = e;
}
int size(){//리스트안의 요소의 개수 반환
  return length;
}

7) 배열로 구현한 리스트

#include<stdio.h>
#include<stdlib.h>
#define MAX_LIST_SIZE 100
typedef int Element;
Element data[MAX_LIST_SIZE];
int length=0;
void error(char* str){
  fprintf(stderr, "%s\n", str);
  exit(1);
}
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){//id위치에 있는 data를 반환
  return data[id];
}
int replace(int id,Element e){//id위치에 있는 data를 e로 교체
  data[id] = e;
}
int size(){//리스트안의 요소의 개수 반환
  return length;
}
void print_list(char* msg){
  printf("%s[%2d]: ",msg,length);
  for(int i=0;i<length;i++)
    printf("%2d ", data[i]);
  printf("\n");
}
void insert(int pos, int e){//리스트의 삽입 연산
  if(is_full()==0 && pos >=0&& pos<=length){//pos=삽입위치, is_full = 꽉차있는지 확인
    for(int i=length;i>pos;i--)
      data[i]=data[i-1];//data를 삽입하고 밀어내기
    data[pos] = e;// 삽입할 값을 pos에 집어넣기
    length++;//리스트를 삽입할 때 length를 증가시켜 크기가 꽉차지 않게 함.
  }
  else error("포화상태 오류 또는 삽입 위치 오류");
}
void delete(int pos){//리스트의 삭제 연산
  if(is_empty()==0 && 0<=pos && pos<length){//is_empty() = 리스트가 비어있는지 확인, pos = 새로운 값을 삽입하는 위치
    for(int i=pos+1;i<length;i++){
        data[i-1] = data[i];//뒤에있는 항목들을 앞으로 당겨줌
      length--;//삭제가 끝나면 길이를 하나 줄여줌.
    }
  }
  else error("공백상태 오류 또는 삭제 위치 오류");
}
int find(Element e){//리스트의 탐색연산
  for(int i = 0;i<length;i++)
    if(data[i]==e)//찾으려고 하는 값 e를 찾으면 그때의 인덱스 id를 반환.
      return i;
    return -1;//같은 항목이 없으면 -1을 반환
}
int main(){
  init_list();
  insert(0,10);
  insert(0, 20);
  insert(1,30);
  insert(size(), 40);
  insert(2,50);
  print_list("배열로 구현한 List(삽입x5)");
  replace(2,90);
  print_list("배열로 구현한 List(교체x1)");
  delete(2);
  delete(size() - 1);
  delete(0);
  print_list("배열로 구현한 List(삭제x3)");
  clear_list();
  print_list("배열로 구현한 List(정리후)");
}