연결 리스트 (Linked List) - 배열

* 열혈강의 자료구조 책 + 인터넷 + a

책이 정말 너무 잘 되어있지만 여기엔 간단하게 씀 + 내상각 추가

순차 리스트 (배열 기반) 

순차적으로 접근할 수 있는, 구조체와 배열을 이용한 연결 리스트이다.

1. 배열 기반의 구조체 정의

typedef struct _ArrayList{ int arr[100]; int numOfData; //데이터의 개수 int curPosition; //배열의 인덱스 값 저장 } List; //구조체 이름을 List로 정의

2. 구조체 기반 함수 정의(기능 위주)

void ListInit(List *list){ //리스트 초기화 list->numOfData = 0; //리스트에 저장된 내용이 없다 list->curPosition = -1; //아무것도 저장하지 않음을 의미 } void Insert(List *list, int data){ //리스트에 원소 삽입 if ((list->numOfData)==100){ //만약 리스트에 있는 원소의 개수가 100, 즉 최대치라면 cout<<"Array is already full"<<endl; return; //배열 리스트에 더이상의 원소 삽입이 불가능하므로 리턴 } // 배열 리스트에 남은 공간이 있다면 list->arr[list->numOfData] = data; //구조체 내부 배열에, 데이터 값 삽입 (list->numOfData)++; //데이터가 삽입되었으므로 배열의 원소 갯수가 1 증가 } int First(List *list, int *data){ //배열 리스트의 첫 번째 원소의 유무 리턴 if ((list->numOfData)==0) return false; //만약 리스트의 원소 갯수가 0이라면 아무런 원소가 없는 것이므로 false 리턴 //원소 개수가 1 이상이라면 list->curPosition = 0; //리스트의 인덱스는 0, 즉 첫 번째 원소를 나타냄 *data = list->arr[0]; //첫 번째 원소의 값을 변수에 저장 return true; //저장 성공했으므로 true 리턴 } int Next(List *list, int *data){ //First 함수를 기반으로 만들어진 Next함수이며, //현재 데이터 위치에서 다음 데이터의 위치를 얻는다 //리스트에서 현재 원소의 위치의 다음 위치가 원소의 총 개수보다 크다면, //즉 뒤에 더이상의 원소가 없을 때 false 리턴 if ((list->curPosition)+1 >= list->numOfData) return false; // 원소가 뒤에 존재한다면 (list->curPosition)++; //현재 원소의 위치를 한 칸 뒤로 이동 *data = list->arr[list->curPosition]; //변수에 값을 저장 return true; //저장 성공했으므로 true 리턴 } int Remove (List *list){ //데이터 삭제 int removedData = list->arr[list->curPosition]; //현재 위치의 원소를 삭제할 것이다 for (int i=(list->curPosition);i<(list->numOfData)-1;i++){ //현재 위치의 값이 삭제되므로 현재 위치 뒤에 있는 모든 원소들을 한 칸씩 앞으로 땡긴다 list->arr[i]=list->arr[i+1]; } (list->curPosition)--; //현재 위치를 한 칸 앞으로 땡기고 (list->numOfData)--; //배열 리스트 원소의 총 갯수도 하나 줄어든다 return removedData; //삭제된 원소 값 리턴 } /* 위 코드에서는 저렇게 해놨지만 실제로 이것처럼 다른 변수에 저 값들을 저장하는 것이 속도 면에서 낫다! 근데 그냥 저렇게 했다 int Remove (List *list){ int removedData = list->arr[list->curPosition]; int a = (list->curPosition); int b = (list->numOfData)-1; for (int i=a;i<b;i++){ list->arr[i]=list->arr[i+1]; } (list->curPosition)--; (list->numOfData)--; return removedData; } */ int Count(List *list){ return list->numOfData; //리스트의 총 원소 개수를 리턴 }

3. 테스트용 메인 함수

int main(){ /////List생성, 초기화 List ArrList; int data; ListInit(&ArrList); /////삽입 Insert(&ArrList, 1); Insert(&ArrList, 2); Insert(&ArrList, 3); /////List 원소 개수 출력 cout<<"List 원소의 개수: "<<Count(&ArrList)<<endl; /////저장된 데이터 출력 if (First(&ArrList, &data)){ cout<<data<<endl; while(Next(&ArrList, &data)) cout<<data<<endl; } cout<<endl<<endl; /////숫자 2 탐색하여 삭제 if (First(&ArrList, &data)){ if (data==2) Remove(&ArrList); while(Next(&ArrList, &data)){ if (data==2) Remove(&ArrList); } } /////삭제 후 남은 데이터 전체출력 if (First(&ArrList, &data)){ cout<<data<<endl; while(Next(&ArrList, &data)) cout<<data<<endl; } return 0; }

4. 결과

그렇다면 이번엔 리스트에 구조체 변수를 저장해보고자 한다.

1. 구조체 변수 정의

typedef struct _Point{ int x; int y; } Point; void ShowPoint (Point *data){ cout<<"["<<data->x<<" "<<data->y<<"]"<<endl; } void SetPoint (Point *p, int a, int b){ p->x = a; p->y = b; }

2. 변경된 배열 리스트 구조체 기반 함수 정의(기능 위주)

void ListInit(List *list){ list->numOfData = 0; list->curPosition = -1; } void Insert(List *list, Point *data){ if ((list->numOfData)==100){ cout<<"Array is already full"<<endl; return; } list->arr[list->numOfData] = *data; (list->numOfData)++; } int First(List *list, Point *data){ if ((list->numOfData)==0) return false; list->curPosition = 0; *data = list->arr[0]; return true; } int Next(List *list, Point *data){ if ((list->curPosition)+1 >= list->numOfData) return false; (list->curPosition)++; *data = list->arr[list->curPosition]; return true; } int Count(List *list){ return list->numOfData; }

- 보면 함수의 매개변수로 모드 int *data라고 하고있는데 책에서처럼 아예 typedef int Data 를 정의해서 int *data 대신 Data *data라고 하는게 좋다..ㅠ

  결론은 변경할 게 딱히 없다

- 임의로 Remove함수를 삭제했는데 나중에 시간이 되면 책에 있는 것과 다른 방식으로 넣어볼 예정

3. 테스트용 메인 함수

int main(){ /////List생성, 초기화 List ArrList; Point data; ListInit(&ArrList); Point *p; p = (Point*)malloc(sizeof(Point)); SetPoint(p, 1, 1); Insert(&ArrList, p); //삽입 p = (Point*)malloc(sizeof(Point)); SetPoint(p, 2, 2); Insert(&ArrList, p); //삽입 p = (Point*)malloc(sizeof(Point)); SetPoint(p, 3, 3); Insert(&ArrList, p); //삽입 /////List 원소 개수 출력 cout<<"List 원소의 개수: "<<Count(&ArrList)<<endl; /////저장된 데이터 출력 if (First(&ArrList, &data)){ ShowPoint(&data); while(Next(&ArrList, &data)) ShowPoint(&data); } return 0; }

4. 결과