5 장. 리스트 리스트 목록이나도표처럼여러데이터를관리할수있는자료형을추상화 데이터삽입, 삭제, 검색등필요작업을가함 스택과큐는리스트의특수한경우에해당 학습목표 추상자료형리스트개념과필요작업을이해한다. 배열로구현하는방법, 연결리스트로구현하는방법을숙지한다. C 로구현할때와 C++ 로구현할때의차이점을이해한다. 자료구조로서배열과연결리스트의장단점을이해한다. 1
목록 ( 도표 ) Position Name Quantity 1 Beer 10 2 Gum 5 3 Apple 4 4 Potato 8 5 Onion 8......... 2
추상자료형리스트의작업 Insert(Position, Data) 데이터를해당위치 (Position) 에넣기 Delete(Position) 해당위치 (Position) 의데이터를삭제 Retrieve(Position, Data) 해당위치 (Position) 의데이터를 Data 변수에복사 Create( ) 빈리스트만들기 ( 종이준비 ) Destroy( ) 리스트없애기 ( 종이버리기 ) IsEmpty( ) 빈리스트인지확인 ( 아무것도안적혔는지확인 ) Length( ) 몇개의항목인지계산 ( 몇개나적혔는지세기 ) 3
공리 추상자료형의작업을형식화 공리 리스트공리 (alist.create( )).Length( ) = 0 (alist.insert(i, Data)).Length( ) = alist.length( ) + 1 (alist.create( )).IsEmpty( ) = TRUE (alist.insert(i, Data)).Delete(i) = alist (alist.create( )).Delete(i) = ERROR Insert(1, Ramen) 밀릴것인가, 지울것인가공리로도명시하기어려움인터페이스파일에정확한커멘트를요함 4
C 배열에의한리스트 구조체 카운트변수 데이터배열 Count Data[ ] 2 0 1 2... (MAX-1) 324 256 5
C 배열에의한리스트 코드 5-1: ListA.h (C Interface by Array) #define MAX 100 최대 100개데이터를저장 typedef struct { int Count; 리스트길이 ( 데이터개수 ) 를추적 int Data[MAX]; 리스트데이터는정수형 listtype; 리스트타입은구조체 void Insert(listType *Lptr, int Position, int Item): 해당위치에데이터를삽입 void Delete(listType *Lptr, int Position); 해당위치데이터를삭제 void Retrieve(listType *Lptr, int Position, int *ItemPtr); 찾은데이터를 *ItemPtr에넣음 void Init(listType *Lptr); 초기화 bool IsEmpty(listType *Lptr); 비어있는지확인 int Length(listType *Lptr); 리스트내데이터개수 6
C 배열에의한리스트 void Insert(listType *Lptr, int Position, int Item): 자료구조를함수호출의파라미터로전달리스트를가리키는포인터를 Lptr 로복사해달라는것 C 언어로구현할때일반특성으로서전역변수를회피하기위함 void Insert(listType *Lptr, int Position, int Item): 삽입, 삭제는원본자체를바꾸는작업이므로참조호출이필요리스트자체데이터는복사되지않음. 복사에따른시간도줄어든다. void Retrieve(listType *Lptr, int Position, int *ItemPtr); 호출함수의원본데이터를가리키는포인터값을 ItemPtr로 *ItemPtr를변형하면호출함수의원본데이터값이변함 void main( ) { listtype List1; int Result; Insert(&List1, 1, 23); 리스트처음에 23을넣기 Retrieve(&List1, 1, &Result); 리스트의첫데이터를 Result 에넣기 7
C 배열에의한리스트 코드 5-2: ListA.c (C Implementation by Array) #include <ListA.h> 헤더파일을포함 void Init(listType *Lptr) 초기화루틴 { Lptr->Count = 0; 데이터수를 0으로세팅 bool IsEmpty(listType *Lptr) 비어있는지확인하는함수 { return (Lptr->Count = = 0); 빈리스트라면 TRUE void Insert(listType *Lptr, int Position, int Item) 삽입함수 { if (Lptr->Count = = MAX) 현재꽉찬리스트 printf("list Full"); else if ((Position > (Lptr->Count+1)) (Position < 1)) printf("position out of Range"); 이격된삽입위치불허 else { for (int i = (Lptr->Count-1); i >= (Position-1); i--) 끝에서부터삽입위치까지 Lptr->Data[i+1] = Lptr->Data[i]; 오른쪽으로한칸씩이동 Lptr->Data[Position-1] = Item; 원하는위치에삽입 Lptr->Count += 1; 리스트길이늘림 8
연결리스트기초 typedef struct { int Data; 노드내부의실제데이터또는레코드 node* Next; Next 가가리키는것은 node 타입 node; 구조체에 node 라는새로운타입명부여 typedef node* Nptr; Nptr p, q; Nptr 타입이가리키는것은 node 타입 Nptr 타입변수 p, q 를선언 9
연결리스트 연결리스트개념 10
연결리스트기초 노드만들기, 이어붙이기 p = (node *)malloc(sizeof(node)); p->data = 33; p->next = (node *)malloc(sizeof(node)); p->next->data = 22; p->next->next = NULL; 11
연결리스트기초 공간반납 Nptr Head; Head = (node *)malloc(sizeof(node)); Head -> Data = 11; Head -> Next = NULL Head = NULL; 12
연결리스트기본조작 디스플레이 Temp = Head; While (Temp!= NULL) { printf("%d ", Temp->Data); Temp = Temp->Next; 13
연결리스트기본조작 간단한삽입 p = (node *)malloc(sizeof(node)); p->data = 8; p->next = Temp->Next; Temp->Next = p; 14
연결리스트기본조작 간단한삭제 p = Temp->Next; Temp->Next = Temp->Next->Next; free p; 15
C 연결리스트에의한리스트 C 연결리스트에의한리스트 16
C 연결리스트에의한리스트 코드 5-3: ListP.h (C Interface by Linked List) typedef struct { int Data; 노드내부의실제데이터또는레코드 node* Next; Next가가리키는것은 node 타입, 즉자기자신타입 node; 구조체에 node라는새로운타입명부여 typedef node* Nptr; Nptr 타입이가리키는것은 node 타입 typedef struct { int Count; 리스트길이를추적 Nptr Head; 헤드포인터로리스트전체를대변함 listtype; void Insert(listType *Lptr, int Position, int Item): 해당위치에데이터를삽입 void Delete(listType *Lptr, int Position); 해당위치데이터를삭제 void Retrieve(listType *Lptr, int Position, int *ItemPtr); void Init(listType *Lptr); 초기화 bool IsEmpty(listType *Lptr); 비어있는지확인 int Length(listType *Lptr); 리스트내데이터수 17
C 연결리스트에의한리스트 코드 5-4: ListP.c (C Implementation by Linked List) #include <ListP.h> 헤더파일을포함 void Init(listType *Lptr) { Lptr->Count = 0; 리스트길이를 0 으로초기화 Head = NULL; 헤드포인터를널로초기화 bool IsEmpty(listType *Lptr) 빈리스트인지확인하기 { return (Lptr->Count = = 0); 리스트길이가 0 이면빈리스트 18
C 연결리스트에의한리스트 코드 5-4: ListP.c (C Implementation by Linked List) void Insert(listType *Lptr, int Position, int Item) 삽입함수 { if ((Position > (Lptr->Count+1)) (Position < 1)) printf("position out of Range"); 이격된삽입위치불허 else { Nptr p = (node *)malloc(sizeof(node)); 확보 삽입될노드의공간 p->data = Item; 데이터값복사 if (Position = = 1) 첫위치에삽입할경우 { p->next = Lptr->Head; 삽입노드가현재첫노드를가리킴 Lptr->Head = p; 헤드가삽입노드를가리키게 else 첫위치가아닐경우 { Nptr Temp = Lptr->Head; 헤드포인터를 Temp로복사 for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; Temp가삽입직전노드를가리키게 p->next = Temp->Next; 삽입노드의 Next를세팅 Temp->Next = p; 직전노드가삽입된노드를가리키게 Lptr->Count += 1; 리스트길이늘림 19
연결리스트 배열과연결리스트비교 ( 삽입 ) 공간이꽉차있는지테스트할필요가없음얼마든지동적으로새로운노드를추가가능중간위치삽입에따른밀림 (Shift) 이불필요삽입직전노드를찾아가는작업이배열에비해오래걸림배열 : 직접접근연결리스트 : 포인터를따라서리스트순회 20
C 연결리스트에의한리스트 코드 5-5: 위치기반연결리스트의삭제 void Delete(listType *Lptr, int Position) 삭제함수 { if (IsEmpty(Lptr)) printf("deletion on Empty List"); 빈리스트에서삭제요구는오류 else if (Position > (Lptr->Count) (Position < 1)) printf("position out of Range"); 삭제위치가현재데이터범위 를벗어남 else { if (Position = = 1) 첫노드를삭제하는경우 { Nptr p = Lptr->Head; 삭제될노드를가리키는포 인터를백업 Lptr->Head = Lptr->Head->Next; 헤드가둘째노드를가리키게 else { for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; Temp가삭제직전노드를가리키게 Nptr p = Temp->Next; 삭제될노드를가리키는포인터를백업 Temp->Next = p->next; 직전노드가삭제될노드다음을가리키 게 Lptr->Count -= 1; 리스트길이줄임 free (p); 메모리공간반납 21
C 연결리스트에의한리스트 값기반연결리스트의삭제 Temp = Lptr->Head; while((temp!= NULL) && (Temp->Data!= Item) Temp = Temp->Next; 이코드로는템프가삭제직전에놓이게할수없음 22
예견방식 Temp = Lptr->Head; C 연결리스트에의한리스트 while((temp!= NULL) && (Temp->Next->Data!= Item) Temp = Temp->Next; 데이터 15 인노드삭제 Temp 가데이터 12 인노드를가리킬때, Temp 는널이아니지만 Temp->Next 는널임. 23
C 연결리스트에의한리스트 코드 5-6 정렬된연결리스트의삭제 Delete(listType *Lptr, int Item) 삭제함수 { Nptr Prev = NULL; Prev는널로초기화 Nptr Temp = Lptr->Head; Temp는헤드로초기화 while((temp!= NULL) && (Temp->Data!= Item) { Prev = Temp; Prev가 Temp를가리키게 Temp = Temp->Next; Temp는다음노드로전진 if (Prev = = NULL) Temp가한번도전진하지않았음 { if (Temp = = NULL) 처음부터빈리스트 printf("no Nodes to Delete"); else 삭제대상이첫노드 { Lptr->Head = Lptr->Head->Next; free (Temp); Lptr->Count - = 1; else Temp가전진했음 { if (Temp = = NULL) 리스트끝까지삭제대상이없음 printf("no Such Nodes"); else 삭제대상이내부에있음 { Prev->Next = Temp -> Next; 직전노드가삭제될다음노드를가리킴 free (Temp); Lptr->Count - = 1; 24
typedef struct { int Data; 이중연결리스트 node* Prev, Next; Prev는이전노드를, Next는다음노드 를가리킴 node; 25
단순연결리스트의삽입 이중연결리스트 테일포인터가따로있으면유리 삭제일경우에는테일포인터가뒤로이동. 이중연결이어야테일포인터를뒤로이동할수있음. 26
원형연결 원형연결, 원형이중연결 타임셰어링시스템의타임슬라이스사용자교대 원형이중연결 27
C 배열과 C++ 배열비교 ListA.h (C++ Interface by Array) ListA.h (C Interface by Array) const int MAX = 100; #define MAX 100 class listclass { public: listclass( ); listclass(const listclass& L); ~listclass( ); void Insert(int Position, int Item); void Delete(int Position); void Retrieve(int Position, int & Item); bool IsEmpty( ); int Length( ); void Init(listType *Lptr); void Insert(listType *Lptr, int Position, int Item) void Delete(listType *Lptr, int Position); void Retrieve(listType *Lptr, int Position, int *ItemPtr); bool IsEmpty(listType *Lptr); int Length(listType *Lptr); private: typedef struct int Count; { int Count; int Data[MAX]; int Data[MAX]; listtype; 28
C++ 배열에의한리스트 코드 5-7: ListA.cpp (C++ Implementation by Array) #include <ListA.h> listclass::listclass( ) 생성자 { Count = 0; 리스트길이를 0으로초기화 listclass::~listclass( ) { 소멸자 listclass::listclass(const listclass& L) 복사생성자 { Count = L.Count; 리스트길이를복사 for (int i = 1; i <= L.Count; ++i) 깊은복사에의해배열요소모두를복사 Data[i-1] = L.Data[i-1]; 29
C++ 연결리스트에의한리스트 코드 5-8: ListP.h (C++ Interface by Linked List) typedef struct { int Data; node* Next; node; typedef node* Nptr; class listclass { public: listclass( ); listclass(const listclass& L); ~listclass( ); void Insert(int Position, int Item); void Delete(int Position); void Retrieve(int Position, int& Item); bool IsEmpty( ); int Length( ); private: int Count; Nptr Head; 30
C++ 연결리스트에의한리스트 코드 5-9: ListP.cpp (C++ Implementation by Linked List) #include <ListP.h> listclass::listclass( ) 생성자함수 { Count = 0; 리스트의길이를 0 으로초기화 Head = NULL; 헤드를널로초기화 bool listclass::isempty( ) 빈리스트인지확인하는함수 { return (Count = = 0); 배열길이 0이면 TRUE 31
C++ 연결리스트에의한리스트 코드 5-9: ListP.cpp (C++ Implementation by Linked List) void listclass::delete(int Position) 삭제함수 { Nptr Temp; if (IsEmpty( )) cout << "Deletion on Empty List"; 빈리스트에삭제요구는오류 else if ((Position > Count) (Position < 1)) cout << "Position out of Range"; 삭제위치가현재데이터범위를벗어 남 else { if (Position = = 1) 삭제될노드가첫노드일경우 { Nptr p = Head; 삭제될노드를가리키는포인터를백업 Head = Head->Next; 헤드가둘째노드를가리키게 else 삭제노드가첫노드가아닌경우 { for (int i = 1; i < (Position-1); i++) Temp = Temp->Next; Temp가삭제될노드직전노드로이동 Nptr p = Temp->Next; 삭제될노드를가리키는포인터를백업 Temp->Next = p->next; 직전노드가삭제될노드다음을가리키게 Count - = 1; 리스트길이줄임 delete (p); 메모리공간반납 32
C++ 연결리스트에의한리스트 코드 5-9: ListP.cpp (C++ Implementation by Linked List) listclass::~listclass( ) 소멸자함수 { while (!IsEmpty( )) 리스트가완전히빌때까지 Delete(1); 첫번째것을계속지우기 listclass:listclass(const listclass& L) 복사생성자함수 { Count = L.Count; 일단리스트개수를동일하게 if (L.Head = = NULL) Head = NULL 넘어온게빈리스트라면자신도빈리스트 else { Head = new node; 빈리스트아니라면일단새노드를만들고 Head->Data = L.Head->Data; 데이터복사 Nptr Temp1 = Head; Temp1은사본을순회하는포인터 for (Nptr Temp2=L.Head->Next; Temp2!= NULL; Temp2=Temp2->Next) { Temp1->Next = new node; 사본의현재노드에새노드를붙임 Temp1 = Temp1 -> Next; 새노드로이동 Temp1->Data = Temp2->Data; 새노드에원본데이터를복사 Temp1->Next = NULL; 사본의마지막노드의 Next에널을기입 33
배열과연결리스트의비교 공간배열은정적이므로최대크기를미리예상해야함. 만들어놓은배열공간이실제로쓰이지않으면낭비연결리스트는실행시필요에따라새로운노드생성연결리스트는포인터변수공간을요함 검색시간배열은단번에찾아감 ( 묵시적어드레싱 : 인덱스연산 ) 연결리스트는헤드부터포인터를따라감 ( 현시적어드레싱 : 포인터읽음 ) 삽입, 삭제시간배열의삽입 : 오른쪽밀림 (Shift Right) 배열의삭제 : 왼쪽밀림 (Shift Left) 연결리스트 : 인접노드의포인터만변경 어떤자료구조? 검색위주이면배열이유리삽입삭제위주라면연결리스트가유리최대데이터수가예측불가라면연결리스트 34