삼성 SW 역량테스트 B형/Pro 대비 - 단방향 Linked list 만들기

1. 단방향 Linked list

 Linked list는 하나의 단위로 구성된 Node에 다음 혹은 이전의 Node에 대한 주소 값을 저장하여 연결하는 list를 뜻한다. 배열과 달리 서로 인접하지 않은 메모리 영역에 노드를 저장할 수 있다. 또한 다음 값을 저장하고 있기 때문에 추가나 삭제시에 해당 값만 변경하면 되는 잇점이 있다. 

 

 

 물론 장점만 있는 것은 아니다. 만약 정렬된 상태일 때 배열의 경우 binary search와 같은 기법으로 O(n)의 탐색 시간을 O(logn)까지 떨어트릴 수 있지만, linked list의 경우 full scan을 해야 한다.

 

 

 물론 여기서도 역량테스트 (Certi) B형(Pro) 기준으로, malloc과 같은 동적 할당 없이 구현한다. (free도 없다.)

2. 기본 동작

함수	동작
init	리스트 초기화
alloc	새로운 노드 할당
append	리스트에 주어진 값을 추가
search	리스트에서 주어진 값을 탐색
remove	리스트에서 주어진 값을 삭제
update	리스트에서 주어진 값을 다른 값으로 대체

 

3. 노드 구조체와 리스트

 노드 구조체는 값(val), 삭제 여부(del), 다음 노드를 가르키는 포인터(nx) 총 세 개를 저장한다. 그리고 동적 할당 없이 전역 변수로 50만개를 잡고, 현재 어디까지 사용했는지에 대한 index로 nCnt를 사용한다. (이 nCnt는 init 전까지 순증하므로 반드시 메모리 크기를 확인하고 사용하자)

struct Node {
  int val;
  bool del;
  Node* nx;
};

Node *list;
Node nodes[500005];
int nCnt;

 여기서 list는 별도의 head 구조체를 쓰지 않고 Node*를 사용한다. (개인 취향, 코드가 조금씩 더러워지긴 하는데 head 쓰는 것보다 개인적으로 편리함)

 

 

4. init, alloc 함수

void init() {
  nCnt = 0;
}

Node* alloc(int v) {
  nodes[nCnt].val = v;
  nodes[nCnt].del = 0;
  nodes[nCnt].nx = NULL;
  return &nodes[nCnt++];
}

 init에서는 nCnt만 0으로 초기화한다. nodes 배열 전체를 초기화해도 무방하지만, 어차피 alloc에서 값을 저장하기 위해 access 하므로 alloc에서 할당된 노드만 값을 초기화하는 작업을 한다.

 alloc 함수에서는 val, del, nx를 업데이트 해주고, nCnt를 증가시켜준다. nCnt를 1부터 사용하겠다면, 처음에 ++nCnt해주고 nodes+nCnt로 처리해도 된다. (아니면 새로운 변수에 담아도 무방)

 

 

5. append 함수

Node* append(int v) {
  Node* cur = list;
  Node* newNode = alloc(v);
  if (!cur) 
    return list = newNode;
  while (cur->nx) {
    cur = cur->nx;
  }
  return cur->nx = newNode;
}

 append 함수는 v를 받아서 새로운 노드를 할당한 다음, 리스트의 가장 마지막에 넣는다. 

처음에 list의 타입을 별도의 Head 구조체가 아닌 Node*로 잡았기 때문에 처음 list에 담긴 값이 NULL인지 확인해주는 if문으로 확인한 뒤 list에 새로운 노드를 담아주는 부분이 필요하다.

 

 그 다음부터 cur->nx가 존재하면 계속 다음 노드로 넘어가준다. 루프가 끝나고 나면 항상 cur && !cur->nx 인 상태이므로 cur->nx에 새로운 노드를 담아준다.

 

 

6. search 함수

Node* search(int v) {
  Node* cur = list;
  if (!cur) return NULL;
  while (cur) {
    if (cur->val == v)
      return cur;
    cur = cur->nx;
  }
  return NULL;
}

 append에서와 같이 Node* cur 변수에 담아서 while루프를 이용해 다음으로 계속 이동한다. 이때 찾고자 하는 값이 같으면 반환하면 된다.

 

7. remove 함수

Node* remove(int v) {
  Node* pre = NULL;
  Node* cur = list;
  if (!cur) return NULL;
  while (cur) {
    if (cur->val == v) {
      if (!pre) 
        list = cur->nx;
      else 
        pre->nx = cur->nx;
      cur->del = true;
      return cur;
    }
    pre = cur;
    cur = cur->nx;
  }
  return NULL;
}

 remove 함수는 단방향 linked list 특성상 조금 복잡해지는데, 리스트의 중간을 삭제하게 되면 이전 노드와 그 다음노드를 연결해주어야 한다. 이때 단방향 특성상 이전 노드를 현재 노드만으로는 알 수가 없다. 따라서 이전 노드 정보를 별도의 변수에 담아서 저장해 주어야 한다.

 그리고 마찬가지로 head를 위한 구조체를 사용하지 않아 삭제 되는 지점이 list의 맨앞인지 여부를 확인해야 한다. 만약 양방향 linked list 였다면, 처음 구현한 search를 이용하여 쉽게 구현할 수 있다.

 

 

8. update 함수

Node* update(int v, int c) {
  Node* cur = search(v);
  if (cur) {
    cur->val = c;
  }
  return cur;
}

 업데이트 함수는 search로 찾아진 결과를 바탕으로 값만 변경해주면 된다.

 

 

9. 그 외

Node* appendAfter(int v, int c) {
  Node* cur = search(v);
  Node* newNode;
  if(cur){
    newNode = alloc(c);
    newNode->nx = cur->nx;
    cur->nx = newNode;
  }
  return cur;
}

void printlist() {
  Node* cur = list;
  while (cur) {
    printf("%d, ", cur->val);
    cur = cur->nx;
  }
  printf("\n");
}

 appendAfter와 같이 특정 값 이후에 넣고자 한다면, 이 또한 search로 찾아진 노드의 nx에 새로운 노드를 연결해주고 기존에 저장된 nx 정보를 새로운 노드의 nx에 넣어주면 된다.

 print하는 경우에는 while 루프를 이용하면 쉽게 출력할 수 있다.