연결 리스트 구현

Su.murf·2023년 9월 21일
CNodelinkedlist이중연결리스트

구조체를 사용하여 항상 내림차순으로 정렬되는 이중(양방향) 연결리스트 ADT를 구현하라.

가 이번 커리큘럼 과제되시겠다.

물론 몇 가지 조건들이 있었다.

어떤 함수들을 포함해서 구현하라든가, Node 구조체를 동적할당해서 구현하라든가..

1. Node 구조체

먼저 이전 노드를 가리키는 데이터, 다음 노드를 가리키는 데이터, 정수를 저장할 데이터를 포함한 Node 구조체가 필요했다.

struct Node{
    Node* next; //이전 노드를 가리키는 데이터
    Node* prev; //다음 노드를 가리키는 데이터
    int value; //정수를 저장할 데이터
};

이렇게 자신의 구조체를 가리키는 포인터를 멤버로 갖는 형식을 자기 참조 구조체라고 한다.

2. List 구조체

head와 tail도 만들어 놓자. 참고로 헤드노드(head node)와 테일노드(tail node)는 실질적인 값을 갖는 가장 첫번째와 마지막 노드로, head 앞에 쓰이는 더미 노드(dummy node)인 헤더 노드(header node)가 아니다. 따라서 이 둘은 나중에 전체 코드를 보면 알겠지만 main에서 value값을 넣어줄 것이다.

참고로 나는 더미 노드 없이 리스트를 구현했다.

struct List{
    Node* head;
    Node* tail;
};

3. 함수 구현

이제 함수들이 필요하다. main 함수 이전에 함수 원형들을 선언해준다.

void InsertData(List*, int); //정수를 입력 받아 내림차순으로 리스트에 저장한다.
void DeleteData(List*, int); //입력받은 정수가 리스트에 존재할 경우 삭제한다.
void FindData(List*, int); //입력받은 정수가 앞에서 몇 번째인지 출력한다.
void PrintData(List*); //리스트 전체를 출력한다.

매개변수가 왜 int랑 List*인가요?

라고 묻는다면...

일단 구현해야하는 함수들 설명에 "정수를 입력받아" ,"입력 받은 정수가" 라는 부분이 있으므로 int를 넣었다.

그리고 추가할 매개변수 타입을 Node*와 List* 중에서 고민했었는데,
List가 여러 개일 경우를 대비하여 List*를 넣는 게 관리하기 더 쉬울 거 같았다.

그리고 List가 아니라 List*인 이유는 함수에서 매개변수로 전달하는 건 단순 복사로, 그 함수 스코프 내에서만 해당 List 갖고 놀 수 있기 때문에 주소값을 전달해줘야 원래 List에도 영향이 간다고 알고 있다.

Node 구조체를 동적할당해서 구현하라 했으니까 노드를 새로 만드는 함수를 하나 추가해 놓자.

Node* GetNode(int value) {
    Node* node = new Node;
    node->prev = NULL;
    node->next = NULL;
    node->value = value;
    return node;
}

GetNode함수는 정수 value 값을 전달받아 Node* 타입을 반환한다.

이렇게 new를 이용하여 동적할당하면 나중에 delete로 메모리 해제 시켜줘야한다는 걸 잊지 말자.

참, 사수님에게 연결리스트 배우면서 ->가 연산(뭐 minus, 부등호 그런 거)이 아닌 참조의 의미를 담고 있다는 걸 알게 되었다.

클래스.멤버

할 때 그 . 이랑 비슷한 기능이다. 다만 ->는 포인터가 접근할 때 쓴다.
참고 사이트: https://devbot.tistory.com/70

잠깐 딴 길로 샜는데, 하던 걸로 다시 돌아와보면 이제 main() 밑에다가 아까 main() 위에 원형 선언했던 함수들을 정의해줄 차례이다.

먼저 입력받은 정수를 새 노드로 연결된 노드들 사이에 삽입하는 함수를 만들어보자. 

void InsertData(List* list, int value) {
    Node* p;
    Node* NewNode= GetNode(value);
    
    for (p = list->head;p!=list->tail;p = p->next) {
        //노드들 사이에 노드 추가 삽입 
        if (value <= p->value && value >= p->next->value) {
            NewNode->prev = p;
            p->next->prev = NewNode;
            NewNode->next = p->next;
            p->next = NewNode;
            cout << value << "을(를) 삽입했습니다." << endl;
            break;
        }
    }
}

아까 매개변수 타입들만 열거했던 함수 원형들보다 친절하게 이름까지 정의해준다.

삽입할 노드를 NewNode로 두고, 내림차순으로 정렬될 수 있도록 순서에 주의하여 삽입해준다.

여기서 주의해야할 것은 각 노드들의 팔다리(next, prev)를 끊는 순서이다.

여기서 내가 말하는 '팔다리'는 비유다. 노드 포인터들을 각 노드에 달린 화살표, 팔로 생각하면 이해가 잘 된다.

어쨌든 잘못된 순서로 코드 짜면 null 참조 오류남...
요점은 NewNode의 prev나 next를 먼저 설정해주는 것이다.

범했던 실수(0) ...은 아니고

사실 나는 처음에 위 for문을 이렇게 작성했었다.

for (p = list->head;p->next;p = p->next)
//수정 후: for (p = list->head;p!=list->tail;p = p->next)

for문에서 조건식을 p->next로 작성해서 생겼던 문제가 있었던 거 같은데 지금 다시 보니 없다.
음... 후에 서술하겠지만 PrintData()에서 문제 있어서 출력이 안 나온 걸 제대로 삽입부터 안 되어서 생긴 문제로 착각한 듯.

  • p->next
  • p->next!=NULL
  • p!=list->tail
    위 셋 중 조건식을 어떤 걸로 해도 잘 돌아간다.
    다만 코드가 직관적으로 이해되도록 p!=list->tail로 수정했다.

범했던 실수(1)

다음은 노드를 삭제하는 함수 DeleteData()이다.
이 함수를 짤 때도 굉장히 머리를 싸맸었다.

void DeleteData(List* list, int value){
    Node* cur;

    for (cur = list->head;cur->next!=NULL;cur = cur->next) {
        if (cur->value == cur->next->value) {
            delete cur;
            break;
        }
    }
}

단순히 delete로 생성했던 메모리 해제하면 되겠지~ 싶었는데

deleteData()가 실행된 이후 출력이 나오지 않았다.

cur은 메모리가 해제되어서 없는데 그 후로도 cur이 전제된 for문을 계속 돌려니까 말이 안되어서 그런 듯 했다.

다시 함수를 짜기로 했다.

그래서 내가 생각한 방법은

현재 노드를 이전 노드와 다음 노드와의 연결을 끊고 이전 노드와 다음 노드를 연결시킨다.

였다. 물론 현재 노드 연결부터 끊으면 NULL 참조 오류가 뜰 수 있기 때문에 이전 노드와 다음 노드 연결부터 하고 현재 노드 양 팔을 NULL로 한다.

ㅋㅋㅋ근데 밑줄이 떠서 뭐야? 이러고 봤는데
NULL을 역참조하고 있다는 메시지가 떴다.

아무 일도 일어나지 않았다.(오류메시지도, 원하는 출력 결과도 안 나옴)
그래서 delete cur; 아랫 줄에 break;을 추가했더니 삭제는 되었는데

이게 떴다.

근데 어차피 코드 수정은 필요했다. 왜냐하면 10 7 7 6 5 4 4 3 이렇게 앞에 중복값(7)을 삭제해도 뒤에 연속으로 중복인 애(4)가 또 나타나면 뒤에껀 탐색하지 않은 채로 break으로 탈출해버릴 테니까.

같이 고민해주던 오빠가 아이디어를 줬다.

delete도 NULL도 아예 쓰지 마.

그 말인 즉슨, 어차피 연결해주면 이전 노드는 다음 노드를 가리키고 있으니까 현재 노드는 자기만 손(prev,next) 뻗은 채로 제 기능을 못하지 않을까..? 라는 것이 그의 생각.

void DeleteData(List* list, int value){
    Node* cur;

    for (cur = list->head;cur!= list->tail;cur = cur->next) {
        if (cur->value == cur->next->value) {
            cur->next->prev = cur->prev;
            cur->prev->next = cur->next;
            cout << cur->value << "을(를) 삭제했습니다." << endl;
        }
    }
}

난 현재 노드가 끊어지지않고 여전히 다 연결되어있으면 뭔 소용이야? 싶었지만

결국 됐다. ㅋㅋㅋㅋㅋㅋㅋㅋ
그러나 이제는 tail의 value값인 0이 출력되지 않는 것이 문제.

범했던 실수(2)

처음에 짰던 리스트 전체를 출력하는 함수 PrintData()는 다음과 같았다.

void PrintData(List* list) { cout << list; }

지금 생각하면 뭔 생각이었지 싶지만 매우 단순하게 짰다.

"리스트를 출력하라!"
.
.
.

그리고 당연하게도 출력이 안됐다.

내가 원하는 건, 정확하게는, 리스트 안의 node들의 각 value값을 전부 출력 하는 걸 보고 싶었던 것이었다.((컴퓨팅적 사고의 중요성)) 따라서 반복문 안에서 각 node들의 value들을 출력하도록 짰다.

//수정ver.1
void PrintData(List* list) { 
    Node* p;

    for (p = list->head;p->next!=NULL;p = p->next) {
        cout << p->value << endl;
    }
 }

여기서 문제는 tail인 0값이 출력이 안 된다는 것이었다.
알고보니 범인은 for문에서 조건식이었다.
tail은 p->next == NULL이기 때문에 조건식을 충족시키지 못하고 출력되지 않은 것이었다. 사수님) 제가 사실 이래서 더미 노드 안 쓰는 연결리스트를 굉장히 싫어합니다.

따라서 다음과 같이 수정하면서 가독성도 높였다. 

//수정ver.2
void PrintData(List* list) { 
    Node* p;
    
    for (p = list->head;p!= NULL;p = p->next) {
        cout << p->value << " ";
    }
    cout << endl;
 }

해결!

범했던 실수(3)

난 분명 선언했는데, 초기화가 되어있지 않는다고 떴다.

내 떈에는 list 안의 head랑 tail을 GetNode()를 통해서 값을 넣어줬으니 초기화했다고 생각했는데 컴퓨터는 아니라고 하니 난감했다.

그래서 다음과 같이 수정했다.

List* 타입 변수를 만든 건 똑같은데 그전에 구조체 변수 list를 선언하고 list1가 list를 가리키도록 했다.

그런데 사수님이 typedef 사용하면 메인함수에서 struct List라고 선언 안 해도 된대서(몰랐음) 앞의 구조체들 뒤에 이름을 붙여줬다.

그에 맞게 main함수도 적절히 다시 씀.

자세히 보면 list1이랑 list도 서로 바꿔줬다.

범했던 실수(4)

.
.
.
띠용!

이런 경고창이 떴다.
Expression: _CrtIsValidHeapPointer(block)이라는 이 메시지를 곧바로 구글링해보았다. 참고 사이트 클릭

이미 해제된 메모리 영역에 대해서 명시된 코드에 의해 다시 해제를 시도하려다가 발생하는 메시지라고 한다.

그래서 어디서 중복해서 해제되었거나 소멸되었는지 찾아야 한다.

delete list

new로 할당하지 않은 list 메모리를 해제해서 그런 것 같다.

난 어차피 노드들이 동적할당으로 구현되어있고, 그 노드들이 어차피 list 안에 있으니까 일일히 노드 메모리 해제하기 싫어서 delete list로 승부보려고 했던 건데, 음... 얌전히 일일히 해제해주기로 했다.

이제 경고창이 안 뜬다.
해결!

4. 전체 코드

// HandinHand.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
// 구조체를 사용하여 항상 내림차순으로 정렬되는 이중(양방향) 연결 리스트 ADT를 구현하라.

#include <iostream>
using namespace std;

typedef struct Node{
    Node* next; //이전 노드를 가리키는 데이터
    Node* prev; //다음 노드를 가리키는 데이터
    int value; //정수를 저장할 데이터
}Node;

//head와 tail도 구현
typedef struct List{
    Node* head;
    Node* tail;
}List;

void InsertData(List*, int); //정수를 입력 받아 내림차순으로 리스트에 저장한다.
void DeleteData(List*, int); //입력받은 정수가 리스트에 존재할 경우 삭제한다.
void FindData(List*, int); //입력받은 정수가 앞에서 몇 번째인지 출력한다.
void PrintData(List*); //리스트 전체를 출력한다.

//Node 구조체를 동적할당하여 구현
Node* GetNode(int value) {
    Node* node = new Node;
    node->prev = NULL;
    node->next = NULL;
    node->value = value;
    return node;
}


int main()
{     
    //선언
    List list1;
    List* list = &list1;

    //초기화
    list1.head = GetNode(10);   
    list1.tail = GetNode(0);
    //head, tail 연결
    list1.head->next = list1.tail;
    list1.tail->prev = list1.head;

    //Test Funcs
    InsertData(list, 3);
    PrintData(list);

    InsertData(list, 6);
    PrintData(list);

    InsertData(list, 5);
    InsertData(list, 4);
    InsertData(list, 7);
    InsertData(list, 7);

    FindData(list,4);
    PrintData(list);

    DeleteData(list, 7);
    FindData(list, 4);

    InsertData(list, 1);
    InsertData(list, 1);
    PrintData(list);
    DeleteData(list, 1);
    PrintData(list);

    //초기화
    Node* p;

    for (p = list1.head;p != NULL;p = p->next) {
        delete p;
    }
    delete list;
}

void InsertData(List* list, int value) {
    Node* p;
    Node* NewNode= GetNode(value);
    
    for (p = list->head;p!=list->tail;p = p->next) {
        //노드들 사이에 노드 추가 삽입 
        if (value <= p->value && value >= p->next->value) {
            NewNode->prev = p;
            p->next->prev = NewNode;
            NewNode->next = p->next;
            p->next = NewNode;
            cout << value << "을(를) 삽입했습니다." << endl;
            break;
        }
    }
}
void DeleteData(List* list, int value){
    Node* cur;

    for (cur = list->head;cur!= list->tail;cur = cur->next) {
        if (cur->value == cur->next->value) {
            cur->next->prev = cur->prev;
            cur->prev->next = cur->next;
            cout << cur->value << "을(를) 삭제했습니다." << endl;
        }
    }
}
void FindData(List* list, int value){
    Node* p;
    int order = 0;

    for (p = list->head;p != list->tail;p = p->next) {
        order++;
        if (value == p->value) {
            cout << value << "는 "<< order << "번째에 위치하고 있습니다."<<endl;
            break;
        }
    }
}
void PrintData(List* list) { 
    Node* p;
    
    for (p = list->head;p!= NULL;p = p->next) {
        cout << p->value << " ";
    }
    cout << endl;
 }

번외) 찾았다 실수(5)!

velog 쓰다가 이제 깨달은 건데...DeleteData()... 입력받은 value 값이 뭐든 간에 전체 리스트에서 연속으로 중복된 값이 있으면 삭제해버린다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 아놔.

if (value == cur->value)

해
치
웠
나
.
.
.

?

[ 10 7 7 6 3 1 1 0 ]
Ex) DeleteData(1) 실행 시

  • 10 7 7 6 3 0 (X)
  • 10 7 76 3 1 0 (O)

중복된 값이 있을 경우 해당 데이터가 전부 삭제되므로 하나만 지워지도록 break;를 넣어주자...

  for (cur = list->head;cur!=list->tail;cur = cur->next) {
        if (value == cur->value) {
            cur->next->prev = cur->prev;
            cur->prev->next = cur->next;
            cout << cur->value << "을(를) 삭제했습니다." << endl;
            break;
        }
    }

피드백, 훈수 환영^____^

profile
Su.murf
춤을 추며 절망이랑 싸울 거야♬
다음 포스트

코딩자율학습단 5기 후기

0개의 댓글