리스트의 개념
리스트는 '물품이나 명칭 따위들을 일정한 순서로 적어 놓은 것'이라고 정의됩니다. 중요한 것은 일정한 순서를 이해해야 하는데 앞서 배열에서는 인덱스로 표현되는 순서가 배열원소의 메모리공간에서 물리적인 위치를 순서적으로 결정하는 특징을 공부했었다. 리스트에서의 순서는 어떤 정의에 의해 결정된 논리적인 순서라고 이해할 수 있다. 배열은 메모리 공간에서 물리적 순서를 의미했고, 리스트의 순서는 그런 것과 상관없이 사람들의 머릿속에 인식되는 논리적인 순서 또는 의미적 순서를 의미한다.
- 리스트 : 원소들 간의 순서가 지켜지며 유지되는 자료구조
- 리스트의 원소들 간의 순서 데이터가 저장되는 물리적 순서와 상관없이 인식되는 논리적인 순서/의미적 인순서
숫자 2,6,8,9를 예로 들어보자.
배열에서는 4라는 숫자를 입력하면 5번째에 위치에 저장해 주는 개념이라면 리스트는 작은 수부터 정렬하라는 논리적 순서로 2 다음과 6 사이에 저장되어야 할 것이다.
리스트는 논리적인 순서만 따르면 되기에 저장위치를 연속적으로 메모리에 할당할 필요는 없다. 하지만 올바른 순서로 정열을 해주기 위해 순서를 표현해 줄 수 있는 프로그램기법이 필요한데 원소 다음에 오는 원소를 가리키는 주소에 관한 정보를 함께 저장해야 한다.
- 원소값을 저장하는 공간과 다음원소를 가리키는 위치정보를 저장하는 공간을 함께 구현하는 방법
- 배열을 이용하여 리스트를 구현하는 방법
배열을 이용한 리스트의 구현
배열을 용하면 구현된 리스트에서 원소를 삽입하거나 삭제하기 위해서 해당원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 당겨야만하다보니 실제 IT서비스 환경에서는 자주 사용되지는 않는다.
포인터를 이용한 리스트의 구현
포인터를 이용하는 방법은 원소의 자리(메모리)에는 원소값을 저장하고 다음원소를 가리키는 정의의 자리에는 다음 원소가 저장될 위치의 주소값(포인터)을 저장하는 것을 말한다. 이러한 리스트의 원소와 다음 원소값을 가리키는 자리를 합하여 노드라고 하고 노드에는 데이터요소와 포인터가 있다. 이포인터를 링크라고 합니다. 이렇게 구현된 리스트를 연결리스트라고 한다.
- 리스트의 노드 : 원소값과 다음 원소를 가리키는 위치의 주소값으로 구성된 자료단위, 데이터요소인 원소와 리스트의 다음 원소를 알리는 포인터(주소)를 가지는 자료단위
- 포인터 : 메모리에 저장되는 값의 저장 위치에 대한 주소를 가리키는 데이터형
연결리스트는 노드 간의 포인터 연결을 통해서 구현되고, 각 노드는 적어도 두 종류의 필드인 원소값을 저장하는 데이터 필드와 노드 연결을 위한 링크 필드를 가진다. 노드는 C프로그래밍에서 struct자료형으로 구현되고 링크필드는 포인터 변수를 이용하여 구현한다.
- 시작노드는 리스트의 첫 번째 원소를 가리킨다 위에서는 100이다.
- 마지막 노드의 링크는 더 이상 가리킬 것이 없는 널 포인터로 표현한다.
포인터 변수
이번 파트에서는 원소값과 우너소를 지정하는 정보(포인터, 링크)를 담는 노드와 다음 원소를 지정하는 포인터를 이해해 봐야 합니다. 포인터는 메모리의 주소값을 저장하는 변수이다. 결국 변수기에 자료형인 int, float, char 등으로 변수타입을 정해야 한다.
int a;
int *p_a; // 변수 a와 포인터 변수 p_a를 int형으로 지정
p_a=&a; // 포인터 변수 p_a에 a의 주소값을 저장( &a는 단항연산자. 하나의 피연산자만 있어도 되는 것을 말하고 역참조 연산자라고도 한다.
a=100; // a의 값에 100을 넣는다.
*p_a=200; // p_a가 가리키는 주소(a의 주소)를 찾아가서 200을 저장.
구조체(struck) 포인터 타입
값을 저장하는 부분과 링크를 저장하는 부분을 하나에 상자 안에 들어가게 하는 C 프로그래밍 문법이 구조체입니다.
struct linked_list_node {
int data;
struct linked_list_node *link;
}
실행 중의 구조체 메모리 할당
프로그램을 설계할 때 얼마나 많은 메모리 공간이 필요한지 알 수 없습니다. 이럴 때 공간이 낭비되는 상황을 피하 키위 메모리 공간을 동적으로 할당받을 수 있는 malloc( ) 함수와 포인터 변수의 활용이 필요하다.
int a, *p_a;
float b, *p_b;
p_a = (int *) malloc(sizeof(int));
p_b = (float *) malloc(sizeof(float));
*p_a =10;
*p_b = 3.14;
printf("a is % d, b is % f", *p_a,*p_b);
free(p_a);
free(p_b);
마지막 free함수는 malloc함수로 할당받은 메모리 공간을 없애 버리고 다시 사용할 수 있게 해 준다.
연결리스트에서 노드 삽입과 삭제
- 원래 노드의 순서를 X-Y-Z순의 연결리스크가 있다고 하고 삽입될 것은 A라고 생각해 보자
- 삭제의 경우 Y를 삭제해야 한다면 선행노드인 X의 링크 부분이 Z를 후행노드를 가리키게 한다.
- 삽입의 경우 메모리 공간을 할당받아 노드를 생성하고, X-Z인 상태에서 가운데에 넣는다면 생선 된 A의 링크 부분을 후행인 Z를 가리키고 X부분의 링크 부분을 A를 가리키게 한다.
- 삭제의 경우 필요 없어진 X-A-Z에서 다시 A를 삭제한다면 삭제할 A노드의 선행노드(X)를 찾고 X노드의 링크 부분이 A의 후행인 Z를 가리키게 한다.
연결리스트의 여러 가지 연산프로그램
1. 연결 리스트의 생성
typedef struct ListNode {
int data;
struct LiseNode* link;
} listNode;
typydef struct {
listNode* head;
} linkedList_h;
linkedList_h* createLinkedList_h(void){
linkedList_h* H;
H=(linkedList_h*) malloc(sizeof(linkedList_h));
H→head = NULL;
retrun H;
}
typedef struct 선언문을 사용하여 정의하고 데이터 필드 부분은 정수형 변수를 사용하여 data의 공간을 할당하고 링크 필드 부분은 주소값을 저장하여 가리키고 있어야 하기 때문에 노드 구조의 자료형인 ListNode 포인터를 사용하여 정의한다. 노드의 자료구조의 자료형인 ListNode 포인터는 노드 전체를 가리키는 포인터 변수이다.
맨 앞부분을 헤드노드라고 하고 처음노드를 가리키는 역할을 한다. 헤드 노드는 데이터 필드 부분이 필요 없고 리스트 첫 번째 원소를 가리키기 위한 링크 필드 부분만 필요하여 ListNode를 가리킬 수 있도록 ListNode* head라고 정의한다.
이제 연결 리스트 생성을 위해 헤드 노드인 H부터 생성해야 한다. 프로시저 createLinkedList_h( )는 헤드 노드를 하나 생성하여 반환하는 역할을 수행한다. 헤드노드(linkedList_h)를 가리키는 포인터 변수 H를 선언한다. malloc(sizeof(linkedLst_h) 함수는 헤드노드(linkedList_h)의 크기만큼 메모리 영역을 할당받아 그 메모리 영역에 해당하는 주소를 반환하는 역할을 수행한다 H의 링크 부분인 head에는 아직 가리킬 곳이 없어 NULL값을 저장한다.
2. 연결 리스트의 노드 삽입
앞서 만들었던 헤드 노드 H에 한 개의 노드를 생성하여 10을 넣어보자
void addNode(lnkedList_h* H, int x){ //리스트 마지막 노드에 삽입 연산하여 x값은 10이라고 가정??
listNode* NewNode;
listNode* LastNode ;
NewNode = (listNode*) malloc(sizeof(listNode));
NewNode →data = x;
NewNode →link = NULL;
if(H→head == NULL){
H→head = NewNode;
return;
}
LastNode = H→head;
while(LastNode →lnk!=NULL) LastNode = LastNode →link;
LastNode→link = NewNode;
}
노드를 추가하는 함수이름을 addNode라고 정의하고 새롭게 만들 노드는 NewNode, 연결리스트의 노드들이 많을 경우 마지막노드를 LastNode라고 정의한다.
malloc함수를 사용하여 NewNode의 데이터 공간을 할당받고 주소값을 NewNode라고 저장한다. 쉽게 malloc함수에 의해 새롭게 할당된 메모리 공간을 NewNode가 가리킨다.
NewNode의 데이터 필드 값에는 10을 저장하고 링크필드는 아직 가리키는 주소가 없어 NULL을 저장
현재 연결리스트에 연결된 노드가 없기에 if비교문이 참이 되고 실행된다. 헤드노드 H가 새로 생선 한 노드를 가리킬 수 있도록 H링크 필드에 NewNode값이 저장된다 H→head값으로 100번지 주소값이 저장되고 여기까지는 노드를 한 개 밖에 삽입하지 않았으므로 if구문에서 작업을 수행하고 return 되어 LastNode는 사용되지 않는다.
다시 두 번째 노드를 삽입해 보자 값(20)
addNode함수가 호출되고 새롭게 생성되는 함수는 NewNode라고 하고 마지막 노드를 찾기 위해 LastNode라고 정의한다.
malloc함수를 사용하여 NewNode의 데이터 공간을 메모리에 할당받고 주소값을 NewNode가 저장한다.
NewNode데이터 값에는 20을 저장하고 링크 필드 값에는 아직 가리크는 곳이 없어 NULL을 저장
현재 연결리스트에는 노드가 있으므로 H노드가 앞에서 만든 노드를 가리키고 있다. 데이터 10을 가지고 있는 노드를 기리 키고 있어 if문은 거짓이 되고 실행이 안된다.
LastNode는 H노드의 링크필드를 가리키고 있는 곳을 가리킨다. LastNode의 링크 필드갑이 NULL이므로 while 비교문의 값이 거짓이 되고 실행이 안되고 링크 필드에 NewNode의 주소값을 저장하여 NewNode를 가리킬 수 있도록 한다.
3. 연결리스트의 특정 노드 뒤에 삽입
특정 노드의 위치는 prevNode라고 정의하고 삽입할 노드의 데이터 값과 함께 매개변수로 전달받는다.
리스트 중간에 삽입하는 연산이고 itdata의 값은 5라고 가정하고 보자
void additNode(linkedList_h* prevNode, int itdata){
listNode* NewNode;
NewNode = (listNode*) malloc(sizeof(listNode));
NewNode→ data=itdata;
NewNode→ link=NULL;
NowNode → link=prevNode→link;
prevNode→link = NewNode;
return;
}
연결 리스트에서 특정 노드를 추가하는 함수의 이름을 additNode라고 정하고 연결리스트의 헤드노드(H)에 삽입하고자 하는 노드의 선행 노드 위치를 가리키는 prevNode와 삽입하는 노드의 데이터 값을 매개 변수로 전달을 받게 됩니다.
새롭게 만들고자 하는 노드를 NewNode라고 정의하고 NewNode의 데이터값은 5입니다. malloc함수를 사용해 메모리 공간을 할당받고 주소값을 NewNode라고 저장해 할당된 메모리공간을 NewNode가 가리키도록 한다.
NewNode의 데이터 값에는 5를 저장하고 링크필드는 아직 가리키는 곳이 없어 NULL을 저장한다.
이제 새롭게 생성된 NewNode가 prevNode뒤에 삽입되야 하기 때문에 prevNode가 가리키고 있는 주소 100을 newNode가 가리키게 하고 prevNode는 Newnode를 가리키게 해야 한다. 이때 반드시 prevNode가 가리키고 있는 주소를 NewNode의 주소로 변경시키는 것을 먼저 하면 안 된다 그 이유는 NewNode에 넣어야 할 주소값이 사라지게 되어 오류가 발생된다. 그러므로 특정위치의 노드인 prevNode의 링크값을 NewNode의 링크에 값에 저장하고 다음에 prevNode후행노드가 올 수 있도록 저장한다. 그리고 prevNode의 링크 값에는 NewNode값을 저장한다.
4. 연결 리스트의 노드 삭제
삭제할 때는 연결리스트의 노드가 존재하는지 를 고려해야 한다. 마지막 노드가 삭제되면 선행노드의 링크 필드 값은 NULL 이 되어야 한다. 마지막 노드를 삭제한다는 가정하에 해보자
void deleteNode(linkedList_h* H){
listNode* prevNode;
listNode* delNode;
if(H→head==NULL) retrun // 공백리스트라면 삭제연산 중단
if(H→head→link ==NULL) // 리스트에 노드가 한 개인 경우
free(H→head) //첫 번째 노드의 메모리를 해제
H→head =NULL
return;
}
else { //여러 개의 노드가 있는 경우
prevNode = H→head;
delNode = H→dead→link;
while(delNode→link!=NULL){
prevNode = delNode;
delNode=delNode→link;
}
free(delNode);
prevNode→link=NULL;
}}
연결 리스트의 마지막 노드를 삭제하는 함수이름을 deleteNode 정의
삭제되는 노드의 앞 노드를 가리킬 수 있는 변수가 필요한데 자료형 ListNode 가리키도록 listNode* prevNode정의하고 삭제되는 노드를 가리 킬 수 있는 변수 역시 listNode* delNode; 정의한다.
헤드노드가 가리키는 노드가 없이 NULL값을 가지고 있는 경우는 노드가 없으므로 중지.
if(H→head→link ==NULL)인 경우는 헤드노드가 가리키고 있는 링크의 값이 NULL인 경우인데 이경우는 한 개의 노드만 가지고 있다 할 수 있고 한 개 있는 것을 삭제해 주면 된다. free연산은 더 이상 쓸모없는 메모리 공간을 ㄹ힙 영역에 반환하여 헤드 노드가 가리키는 곳의 메모리 공간을 반환하고 H인 헤드노드가 가리키는 곳이 해제되었으므로 헤드노드(H)의 링크 필드값을 NULL로 저장하고 retrun 한다.
이제는 먼저 H가 가리키는 첫 번째 노드를 prevNode로 가리키고 지워야 하는 노드를 prevNode다음 위치로 정해준다. 그럼 우선 노드가 몇 개든 첫 번째 노드가 prevNode로 그다음이 delNode로 지정되어 있다.
이제는 while문을 반복하여 가장 끝에 있는 노드로 갈 텐데 쉽게 현재 첫 번째와 두 번째에 지정되어 있던 각각 prevNode, delNode는 delNode에 링크 부분이 NULL이 아니라면 prevNode는 delNode가 있는 두 번째 노드로 옮겨오고 delNode는 링크를 따라 그다음 값으로 이동하여 한 칸씩 이동합니다 반복하다 delNode의 이동하려는 값이 NULL이 될 때 whilde문은 종료되게 됩니다.
이제 delNode가 가리키는 곳을 반환하고 마지막 노드가 된 prevNode의 link를 NULL저장하면 됩니다.
5. 연결 리스트의 특정 노드 검색과 삭제
앞서 방법과 같이 헤드노드에서 시작하여 데이터 값을 비교하면서 삭제하려는 노드를 찾아야 하고 일치되는 데이터 노드를 찾았다면 삭제해 주면 된다.
void findandDeleteNode(linkedList_h* H, int itdata){ // 검색 또는 삭제하고자 하는 연산, itdata=10
listNode* prevNode;
listNode* delNode;
if(H→head==NULL) return; // 리스트가 비어있는
prevNode = H;
delNode = H→dead;
while(delNode!= NULL){
if(delNode→data == itdata){
deleteitNode(H, prevNode, delNode);
retrun;}
else {
prevNode = delNode;
delNode=delNode→link;}
}}
삭제되는 노드 앞노드를 가리킬 수 이쓴 변수 prevNode로 정의, 삭제되는 노드를 가리키는 delNode로 정의
헤드 노드(H)의 값이 NULL인 경우 공백리스트이므로 종료
그게 아니라면 가장 처음 노드 앞을 가리킬 수 있도록 prvNode를 H 헤드노드로 정하고 delNode가 첫 번째 노드를 가리도록 한다.
delNode가 NULL이 아닌 경우는 헤드 노드에 노드가 연결되어 있는 경우이고 조건이 참이므로 반복문을 실행.
먼저 메개변수로 전달받은 itdata값과 delNode의 값이 같은지를 비교하고 참인 경우 삭제할 노드를 찾았으므로 특정노드를 삭제하는 deleteitNode를 호출하고 연산을 마치고 return 한다.
거짓이라면 delNode는 다음 노드를 가리켜야 하므로 앞서방법과 마찬가지로 한 칸씩 다음으로 이동하게 되고 다시 while문을 반복하게 된다.
이때 삭제 deleteitNode는 다음과 같이 할 수 있다.
void deleteitNode(linkedList_h* H, listNode* prevNode, listNode* delNolde){
prevNode → link = delNode → link
free(delNode);
retrun;
}
헤드노드(H)와 삭제하고자 하는 노드의 앞의 노드를 가리키는 선행노드 (prevNode)와 삭제할 노드(delNode)를 매개변수로 전달받습니다.
delNode를 삭제할 경우 후행으로 연결된 링크를 알 수 없기에 먼저 선행노드인 prevNode에 삭제할 노드 링크를 넣어주고
delNode가 가리키는 곳에 메모리 공간을 반환하고 연산을 마친다.