#26 [C 자료구조] 단순하지 않은: 단순 연결 리스트

오늘은 단순 연결 리스트의 코딩 법에 대해서 빡세게 알아볼 예정이다.

이전의 #18 자기 참조 구조체의 포스팅을 한 번 보고 오면 도움이 될 것이다.

 

기본적인 연결 리스트를 만드는 문장을 짜보자.

이런 노드를 만들 것이다

0) 공백의 노드 만들기

typedef struct lintNode NODE;
struct listNode {
	int data
    NODE *link;
};

이러면 1개의 데이터와 1개의 주소 값(다른 노드를 가리킬)을 가지는 노드를 만드는 struct를 짠 것이다.

1) 포인터를 생성하고(공백의 포인터를 만들어놔야 노드를 각각 만들 때 메모리 할당이 가능하다.)

NODE *ptr = NULL;

2) 공백 메모리인지 확인한 뒤

#define IS_EMPTY(ptr) (!(ptr))

3) 동적 메모리를 할당해보자

ptr = (NODE*) malloc (sizeof(NODE));

이렇게 공백의 노드와 그 노드를 가리키는 포인터를 만들었다.

요래 말이다!

4) 이러한 노드를 두 개 만들어 서로 연결시켜보자

NODE* create2(){ //두개 노드를 가진 연결 리스트 생성
	NODE *first, *second; //first, second의 메모리를 추후에 할당해줄 것이기 때문
    
    first = (NODE*) malloc(sizeof(NODE));
    second = (NODE*) malloc(sizeof(NODE));
    
    first -> data = 30; 
    (*first).link = second; //주소값
    
    (*second).data = 20;
    second -> link = NULL;
    
    return first;
}

여기서 first -> data와 (*first).data 는 같은 의미이다. 구조체의 값을 바꾸는 방법을 포인터로 단순화한 것!!

0) ~ 4)를 통해 아래와 같은 리스트를 만들었다.

0) ~ 3)의 과정이 반드시 있어야 연결 리스트를 만들 수 있다.

---

 

 

 

단순 연결 리스트 노드 삽입

노드 삽입은 이전 포스팅에서 말했던 개념을 따라가기만 하면 된다.

1) MALLOC() 함수를 통해 사용하지 않는 노드 a를 가져온다.

2) 노드 a의 데이터 필드에 value를 대입한다.

3) a의 Link필드가 다음 노드를 가리키도록 한다.

4) 이전 노드가 삽입된 노드를 가리키도록 한다.

 

이미 있는 2개의 연결 리스트 안에 50의 값을 가지는 노드를 삽입시킬 것이다.

 

이러한 프로세스를 코드로 구현해보자.

void insert(NODE *ptr, NODE *first){ //함수생성
	NODE *temp; //temp가 링크인 노드 생성
    temp = (NODE*) malloc(sizeof(NODE)); //동적 메모리 할당
    temp -> data = 50;
    
    if (ptr) { //ptr이 가리키고 있다면
    	temp -> link = first -> link; //temp가 다음 것을 먼저 가리키게 한다.
        first -> link = temp; //그 다음 이전 것이 temp를 가리키게 한다.
    }
    else { //ptr이 아무것도 가리키지 않는다면
    	temp -> link = NULL;
        ptr = temp;
    }
}

---

 

 

단순 연결 리스트 노드 삭제

노드 삭제는 삽입보다 훨씬 쉽다. 이 것도 오류가 나지 않게 이전 노드를 다음 노드에 연결시켜주고 나서 해당 노드를 삭제하는 방식을 취한다.

코드로 구현해보자

void deletee(NODE *ptr, NODE *first, NODE *temp){
    if (first) //temp앞 노드가 있을 경우
    	first -> link = temp -> link //3번째 노드의 링크르 1한테 줌
    
    else //temp가 첫 노드일 경우
    	ptr = ptr ->link;
        
    free(temp); //temp는 자유에요!
}
        

---

 

 

 

단순 연결 리스트 노드 출력

아주 단순히 노드를 출력하는 코드를 짜 보도록 하자

void printNODE(NODE *ptr){
	printf("노드 값 들어갑니당\n");
    
    for ( ; ptr ; ptr -> link)
    	printf("%d\n", ptr->data);
}

쉽쥬? 

---

 

 

 

가용 공간 리스트 관리

오늘의 가장 어려운 개념이 될 것 같다. 흑흑.

가용공간 리스트란 이제는 사용하지 않는 노드를 체인 형태의 리스트로 만든 것이다.

만드는 목적은 새로운 노드 필요시 리스트를 조사하여 다시 사용하는 것이고

이 리스트가 다 소모되어 없을 때만 malloc()을 사용하고자 하는 것이다.

 

따라서 malloc() 대신 getNode() 를, free() 대신 retNode()를 사용한다.

안 쓰는 노드를 가용 공간에 넣고 빼는 방법을 코드를 통해 알아보즈앗!

 

1) getNode 함수 만들기

polyPointer* getNode(voide){ //polyPointer란 연결 리스트가 있다고 치자
	polyPointer *node;
    if (avail) {{ //가용 노드가 있다면
    	node = avail; //avail의 주소 값을 이전 새로운 node에 박고
        avail = avail -> link; //avail에 다음 노드를 가리키는 주소 값을 박는다
    else //가용 노드가 없다면
    	node = (polyPointer*) malloc(sizeof(polyNode)); //새로운 메모리 할당
    return node;
}

여기서는 새로운 node가 가용 리스트 안에 들어가는 모습을 그렸다.

 

2) retNode 함수 만들기

void retNode(polyPointer *ptr) { //가용노드 avail에 반환
    ptr -> link = avail; //이전 노드에 지우려는 avail노드의 주소 값을 미리 박고
    avail = ptr; // avail이 이전 노드를 가리키게 만듦
}

위 함수는 ptr이 가리키는 *ptr노드를 새로이 만들고 avail 대신  다음 노드를 가리키게 한 다음, avail을 ptr의 가용 노드로 만드는 과정이다.

 

3) cerase 함수 만들기

이 함수는 ptr이 가리키는 원형 리스트 전체를 avail에 반환하는 함수다.

void cerase(polyPointer *ptr) { //ptr이 가리키는 원형 리스트
	polyPointer *temp; //*temp 노드 생성
    if (ptr) {
    	temp = ptr -> link; // 1
        ptr -> link = avail; // 2
        avail = temp; // 3
        ptr = NULL; // 4
    }
}
        

이렇게 해주면 ptr 주소는 노드 값을 잃고, avail에는 1과 4 두 순환 노드가 들어가게 된다.