스스로 도움없이 연결리스트(LinkedList) 구현해보기

이틀전에 본 정처기 실기 시험 내에서 연결리스트, 트리 같은 자료구조에 대한 내용들을 보면서 개념들은 알지만 '내가 지금 직접 짤 수 있을까?'라는 생각을 가지게 되어 오늘은 연결리스트를 만들어 보았다.

일단 연결리스트는 의미있는 데이터들을 담고있는 동일한 구조체 타입들끼리 연결시켜주는 것으로 알고있다. 데이터들과 그 다음 순서로 올 데이터 주소를 담아 연결하는 것. 이 말을 이제 코드로 구현해보자.
구현 환경은 https://pythontutor.com/ 이 사이트를 활용해보기로 하겠다.

구조체 내의 구성은 간단하게 값 1개와 다음에 올 주소로 구성하면

struct Node {
  int value;
  struct Node *p;
};

그리고 이 Node라는 구조체에 대한 배열을 만들기 위해 NODESIZE라는 매크로 정의를 5로 해줬다.

#define NODESIZE 5

이제 배열을 만들어줄건데 예전에는 buffer[256] 이런식으로 해줬다면, 이제는 메모리 할당으로 해주는 습관을 들이면 좋을 것 같아서 malloc으로 할당해줬다.

struct Node *node = malloc(sizeof(struct Node) * NODESIZE);

혹시나 정상적으로 할당되었나 궁금하니 돌려봤는데 확실히 눈에 보여서 좋은 듯?

이렇게 정상적으로 사이즈만큼 배열이 생성된게 보인다!

value를 저장하고 다음 노드와 연결하는 함수를 정의해주겠다.
배열 크기만큼 for문을 돌리면서 적절하게 세팅해주면 되는데, 마지막 배열에는 다음 노드가 없으니 조건문을 달아줘야겠지? NULL로 처리하면 완성!

#include <stdio.h>
#define NODESIZE 5

struct Node {
  int value;
  struct Node *p;
};

void settingValue(struct Node* node) {
  struct Node *currentNode = node;
  
  for(int i = 0; i < NODESIZE; i++) {
    currentNode->value = i + 1;
    if(i < NODESIZE - 1) {
      currentNode->p = currentNode + 1;
      currentNode += 1;
    } else {
      currentNode->p = NULL;
    }
  }
};

int main() {
  struct Node *node = malloc(sizeof(struct Node) * NODESIZE);
  settingValue(node);
  return 0;
}

예전에 배운거라 까먹고 못만들면 어쩌지 싶었는데 완성할 수 있어서 다행이다. 만든 김에 이번 시험에 나온 Reconnect함수까지 도전! 지정한 배열을 맨 앞으로 옮겨서 연결하는 함수인데, 지정한 배열은 이 다음 배열과의 연결을 끊고 맨 앞의 배열과 연결, 연결끊긴 앞 뒤의 배열과의 연결을 해줘야한다.

#include <stdio.h>
#define NODESIZE 5

struct Node {
  int value;
  struct Node *p;
};

void settingValue(struct Node* node) {
  struct Node *currentNode = node;
  
  for(int i = 0; i < NODESIZE; i++) {
    currentNode->value = i + 1;
    if(i < NODESIZE - 1) {
      currentNode->p = currentNode + 1;
      currentNode += 1;
    } else {
      currentNode->p = NULL;
    }
  }
};

struct Node* reconnectNode(struct Node* node, int n) {
  if(n > 0 && n < NODESIZE) {
    struct Node *currentNode = node + n;
    
    if(n != NODESIZE - 1) {
      (currentNode - 1)->p = currentNode->p;
    } else {
      (currentNode - 1)->p = NULL;
    }
    
    currentNode->p = node;
    
    return currentNode;
  }
  return node;
};

int main() {
  struct Node *node = malloc(sizeof(struct Node) * NODESIZE);
  settingValue(node);
  node = reconnectNode(node, 2);
  
  return 0;
}

마지막에 노드가 가리키는 부분을 맨 앞으로 온, 지정한 배열(index = 2)을 반환해 바꿨다.
배열자체 순서를 바꾼게 아니라 연결 순서를 바꿨기때문에 이미지에서는 화살표가 가리키는 곳을 잘봐야한다. 결과적으로 배열 인덱스 2, 0, 1, 3, 4 순서로 잘 연결된 것을 볼 수 있다.

연결리스트의 마지막 노드에 node를 NULL이 아닌 첫노드와 연결해주면 원형 연결리스트가 되니까 각자 해보는 것도 좋겠다. 걱정과 달리 다행히 코드가 깔끔해보이진 않더라도 잘구현해낸 듯 하다!
이 외에도 node를 앞뒤로 연결시키는 이중 연결리스트, 구현이 끝난 후 검색하니 처음들어보는 청크 리스트도 있다.
그리고 이 사이트 라인마다 stack, heap 상태를 그려주니 정말 유용하다. 다들 한번씩 써봤으면 좋겠다.