[Data Structure] Linked List 구현

mincoder·2024년 11월 9일
cppdata structurelinked list

실습 과제

목록 보기
3/4
post-thumbnail

Linked List From Scratch

자료구조 수업시간에 과제로 나온 연결리스트 구현입니다. cpp에 익숙한 상태였지만, 코테용(?)이었기 때문에 실제로 클래스를 써볼 일도 없었고 stl 없이 구현해보는게 너무 막막했습니다. 배울 점도 많은 과제일 것 같아서 한번 글을 써보게 되었습니다. 구현해야할 사항은 다음과 같습니다. 천천히 하나씩 뜯어봅시다.. ㅠㅠ

  • Inserting a value: I 0 25 (0번 인덱스에 25 삽입)
  • Deleting a value: D 25 (25값 삭제)
  • Reverse linked list: R
  • Find a value: F 3 (3의 index 반환)
  • Sub-linked list: S 1 3 (1~3 인덱스의 부분 연결리스트 반환)
  • Count the frequency: C 10 (10의 개수 세기)
  • Sort: T (오름차순 정렬)

Node Class

#include <bits/stdc++.h>
using namespace std;
bool err = false; //에러 시 리스트 출력 안해도 됨

class Node {
public:
    int value;
    Node* next;
    Node(int val) : value(val), next(nullptr) {} //생성자
};

일단 연결리스트는 노드의 연결이기 때문에 Node 클래스가 필요합니다. value와 next라는 이름의 ptr를 멤버변수로 선언합니다. 그리고 생성자로 val를 받아서 멤버변수 value에 할당할 수 있습니다. 위의 생성자를 사용하면 다음과 같이 호출 가능합니다. Node* newNode = new Node(5);

LinkedList Class & Deconstructor

다음은 본격적으로 연결리스트 구현이 시작되는 부분입니다. 

class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    ~LinkedList() {
        Node* cur = head;
        while (cur != nullptr) {
            Node* next = cur->next;
            delete cur;
            cur = next;
        }
    }

head 포인터를 멤버변수로 할당하고, 생성자 및 Deconstructor (한글 표현이 안 떠오르네요..) 를 선언해줍니다. head가 nullptr인 경우에 linked list는 empty 상태이므로, 처음 생성 시에 위와 같이 선언하면 됩니다. 그리고 Deconstructor를 살펴보면, 처음에 head부터 출발하여 마지막(nullptr)에 도달하기 전까지 노드의 삭제를 진행합니다.

Inserting a value

자 이제 위의 과정까지가 문제 풀이에 들어가기 위한 셋업이었습니다. 지정 인덱스에 값을 삽입하는 Insert 연산부터 해봅시다. 

void insert(int k, int v) {
 Node* newNode = new Node(v);

 if (k == 0) {// 처음 위치에 삽입
     newNode->next = head;
     head = newNode;
     return;
 }

 if (k == 99) {// 마지막 위치에 삽입
     if (head == nullptr) {
     newNode->next = head;
     head = newNode;
     return;
 	}//k=99인데 빈 리스트의 경우
     Node* cur = head;
     while (cur->next != nullptr) {//마지막 노드로 이동
         cur = cur->next;
     }
     cur->next = newNode;
     newNode->next = nullptr;
     return;
 }

 Node* cur = head; // 처음과 마지막이 아닌 중간에 삽입
 int p = 0; //인덱스 계산을 위함
 while (cur != nullptr && p < k - 1) { // 삽입 위치 이전까지 이동
     cur = cur->next;
     p++;
 }

 if (cur == nullptr) {
     cout << "err_code=100" << '\n';
     err = true;
     delete newNode;
     return;
 }//에러케이스: cur이 null이 되었다는 것은 인덱스 범위 벗어남

 newNode->next = cur->next; 
 cur->next = newNode;
 //이전노드 -> 다음노드 사이에 이전노드 -> newNode -> 다음노드 형태로 삽입
}

Deleting a node

다음으로 특정 value를 가지는 노드 삭제입니다. 

void remove(int v) {
    if (head == nullptr) {//비어있는 경우는 에러
        cout << "err_code=101" << '\n';
        return;
    }

    if (head->value == v) { //처음 값이 삭제할 값이면 바로 삭제(개이득)
        Node* temp = head;
        head = head->next; //헤드 다음으로 한칸 이동
        delete temp;
        return;
    }

    Node* cur = head;
    while (cur->next != nullptr && cur->next->value != v) {
        cur = cur->next;
    }//삭제할 노드 이전까지 이동

    if (cur->next == nullptr) {
        cout << "err_code=101" << '\n';
        err = true;
        return;//값을 찾지 못함
    }

    Node* del = cur->next;
    cur->next = del->next;
    delete del; // cur -> del -> del.next에서 cur -> del.next로 
}

Reverse

연결리스트 반전 연산입니다.

void reverse() {
    if (head == nullptr) {// 비어있으면 당연히 에러
        cout << "err_code=102" << '\n';
        err = true;
        return;
    }

    Node* prev = nullptr;
    Node* cur = head;
    Node* next = nullptr; 

    while (cur != nullptr) {
        next = cur->next; //1단계: 다음 노드를 미리 저장
        cur->next = prev; //2단계: 현재 노드의 next를 이전 노드로 설정 (반전) 
        prev = cur; //3단계: prev를 현재 노드로 업데이트
        cur = next; //4단계: cur을 다음 노드로 이동
    }

    head = prev;
}

1회차 반복) 첫번째 노드의 next를 nullptr로
2회차 반복) 두번째 노드의 next를 첫번째 노드로

위와 같은 식으로 진행되는데 단번에 이해하기가 까다롭습니다.
(1) -> (2) -> (3) -> (NULL) 이런 연결리스트가
(NULL) <- (1) <- (2) <- (3) 이런 형태로 변형한다고 보시면 됩니다. 마지막에는 head 포인터도 갱신해주면 끝!

Find a value

다음은 값 탐색입니다. 

void find(int v) {
    if (head == nullptr) {//비어 있을 경우 에러
        cout << "err_code=103" << endl;
        err = true;
        return;
    }

    Node* cur = head;
    int idx = 0; //인덱스 저장을 위한 변수

    while (cur != nullptr) { //값을 linear search
        if (cur->value == v) {
            cout << idx << '\n';//인덱스 출력
            return; //얼리 리턴
        }
        cur = cur->next;
        idx++;
    }

    cout << "err_code=103" << '\n'; //리턴 안됐으면 오류
}

Sub-linked list

다음은 sub 연산입니다.

LinkedList* subList(int beg, int end) {
    if (head == nullptr) {// 비어있으면 오류
        cout << "err_code=104" << '\n';
        return nullptr;
    }

    int len = 0;
    Node* cur = head;// 노드 개수 세기
    while (cur != nullptr) {
        len++;
        cur = cur->next;
    }

    if (beg < 0 || end >= len || beg > end) {//에러 케이스
        cout << "err_code=104" << '\n';
        err = true;
        return nullptr;
    }

    LinkedList* sublist = new LinkedList(); //새로운 연결리스트 생성
    cur = head; //헤드 포인터로 초기화
    int idx = 0; 

    while (cur != nullptr && idx <= end) {//sublist에 insert 메소드를 호출하여 값 할당
        if (idx >= beg) {
            sublist->insert(idx-beg, cur->value);
        }
        cur = cur->next;
        idx++;
    }

    return sublist;
}

Count

슬 힘드네요... 이번에는 값을 세는 count 함수입니다. 그래도 지금까지 한 것 중에서는 제일 쉽죠(?) 

int countFrequency(int v) {
    int cnt = 0;
    Node* cur = head;

    while (cur != nullptr) {
        if (cur->value == v) {
            cnt++;
        }
        cur = cur->next;
    }

    return cnt;
}

Sort

대망의 마지막 7번째 sorting 함수입니다. 오름차순으로 연결리스트를 정렬하면 됩니다. 버블정렬의 원리를 사용하여 각 노드를 정렬하는데, 각 노드 ~ 마지막으로 정렬했던 노드 앞 까지를 범위로 교환을 계속 해나가는 원리입니다. 처음에는 무슨 말인지 몰랐는데 다음 글을 보면서 이해가 바로 됐습니다! https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

void sort() {
    if (head == nullptr) {
        cout << "err_code=105" << '\n';
        err = true;
        return;
    }

    bool swapped;
    Node* fptr;
    Node* lptr = nullptr;

    swapped = true;  // 첫 번째 반복에서 반드시 수행되도록 설정

    while (swapped) {
        swapped = false;  // 교환 여부 초기화
        fptr = head;      // fprt은 head로 초기화

        while (fptr->next != lptr) {  // lptr 앞ptr 앞까지 순회
            if (fptr->value > fptr->next->value) {  // 값이 크면 교환
                int temp = fptr->value;
                fptr->value = fptr->next->value;
                fptr->next->value = temp;
                swapped = true;  // 교환이 발생하면 swapped = true
            }
            fptr = fptr->next;  // 다음 노드로 이동
        }
        lptr = fptr;  // lptr을 마지막으로 교환된 노드로 설정
    }
}

printList

 void printList() {
 	if (err) {//에러 발생
         err = false; //다시 초기화
         return; //출력x
      }
    if (head == nullptr) { // 비어 있을 경우
         cout << "NULL"<<'\n'; //널만 출력
         return;
     }
     
     Node* cur = head; 
     while (cur != nullptr) {// 연결리스트 순회하면서
         cout << cur->value;
         if (cur->next != nullptr) {//마지막 노드가 아니면
             cout << " -> "; // 사이에 화살표
         }
         cur = cur->next;
     }
     cout << " -> NULL" << '\n'; //마지막 노드는 널을 가리킴
 }

여기까지가 linked list 클래스 내부에 선언되었던 메소드들입니다! 길고 험난한 과정....ㅠㅠ

main function (input)

메인 함수에서 입력을 받아 switch case 문으로 분기처리하여 출력을 해주면 완성됩니다....!! (혹시나 여기까지 보셨다면 정말 정말 끈기에 박수드립니다.)

int main() {
    LinkedList ll;
    char op;
    while (cin >> op) {
        switch (op) {
        case 'I': {
            int k, v;
            cin >> k >> v;
            ll.insert(k, v);
            ll.printList();
            break;
        }
        case 'D': {
            int v;
            cin >> v;
            ll.remove(v);
            ll.printList();
            break;
        }
        case 'R': {
            ll.reverse();
            ll.printList();
            break;
        }
        case 'F': {
            int v;
            cin >> v;
            ll.find(v);
            break;
        }
        case 'S': {
            int beg, end;
            cin >> beg >> end;
            LinkedList* sub = ll.subList(beg, end);
            sub->printList();
            delete sub;
            break;
        }
        case 'C': {
            int v;
            cin >> v;
            cout << ll.countFrequency(v) << '\n';
            break;
        }
        case 'T': {
            ll.sort();
            ll.printList();
            break;
        }
        default:
            break;
        }
    }
    return 0;
}

Result

예.. 결과는 42점입니다. 더 코드 손보고, 엣지케이스 찾아서 돌아오겠습니다. 라고 했지만 뭐가 문제인지 모르겠습니다.. 주어진 테스트 케이스 10개는 모두 통과하는데 ..... 아무튼(?) 이렇게 42점이지만 만족하고 여기서 마무리하려고 합니다.

profile
mincoder
백문이 불여일타
이전 포스트

[Node.js] 쇼핑몰 페이지 구현

다음 포스트

[Java] Interface를 활용한 정렬 알고리즘 구현

0개의 댓글