[1주차 TIL] KnockOn Bootcamp 연결리스트

• 연결 리스트와 배열의 차이점
• 단일 연결 리스트
• 이중 연결 리스트
• 환형 연결 리스트

1. 리스트와 배열 비교

배열: 생성하는 시점에 배열의 크기를 지정해줘야하고 생성한 후 크기를 변경할 수 없다.

-> 유연하게 크기를 바꿀 수 있는 자료구조: 리스트

2. 연결 리스트(linked list)

• 연결 리스트(링크드 리스트): 노드를 연결해서 만든 리스트라고 해서 붙여진 이름

• 다뤄야 하는 데이터 집합의 크기를 미리 알지 못해도 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 됨!

노드

노드의 구성: 필드(데이터 보관), 포인터(다음 노드와 연결)

//노드 표현
typedef int ElementType;

typedef struct tagNode {
  ElementType Data; //데이터
  struct Node* NextNode; // 노드
} Node;

따라서 위와 같이 노드를 표현할 수 있다.

연산

연결 리스트의 주요 연산은 다음과 같다.

• 노드 생성(CreateNode), 소멸(DestroyNode)
• 노드 추가(AppendNode)
• 노드 탐색(GetNodeAt)
• 노드 삭제(RemoveNode)
• 노드 삽입(InsertAfter, InsertnewHead)

노드 생성/소멸

• 자동 메모리 사용?

Node *SLL_CreateNode(ElementType NewData) {
  Node NewNode; //자동 메모리 사용
  NewNode.Data = NewData;
  NewNode.NextNode = NULL:
  return &NewNode;
}

Node *MyNode = SLL_CreateNode(117);
// 할당되지 않은 메모리를 가리킴

위와 같이 코드를 짜게 되면 문제가 생기는데, NewNode가 존재하는 메모리의 주소를 반환하는 것이 아니라 현재는 제거된 과거의 메모리 주소를 반환한다.

따라서 malloc을 이용하여 정상 작동하는 생성 함수를 만들 수 있다.

Node *SLL_CreateNode(ElementType NewData) {
  Node *NewNode = (Node*)malloc(sizeof(Node));
  NewNode->Data = NewData;
  NewNode->NextNode = NULL;
  return NewNode;
}

void SLL_DestroyNode(Node *Node) {
  free(Node);
} //소멸 함수

free함수는 메모리 주소만 정확히 알면 알아서 처리하므로 소멸 함수는 간단하게 구현 가능하다.

노드 추가

• 연결 리스트 테일 뒤에 새로운 노드를 만들어 연결하는 것.

void SLL_AppendNode(Node **Head,Node *NewNode) {
  if ((*Head) == NULL) *Head = NewNode;
    // 헤드가 없음
  else {
    Node *Tail = (*Head);
    while (Tail->NextNode != NULL) Tail = Tail->NextNode;
    Tail->NextNode = NewNode;
    // 테일(끝)을 찾아 NewNode를 연결.
  }
}

• 매개변수로 Node **Head를 받는 이유

위 함수에서 매개변수를 *Head를 받았다고 가정하고 아래 코드를 실행해본다고 하자.

Node *List = NULL;
Node *NewNode = NULL;
NewNode = SLL_CreateNode(117);
SLL_AppendNode(List, NewNode);

결과적으로는 NewNode가 List에 추가되지 않는다.
코드의 실행 과정을 살펴보면

1. List와 NewNode가 아무 메모리도 가리키지 않는 상태로 초기화
2. NewNode = SLL_Createnode(117); 실행 후 자유 저장소에 117을 가진 노드 생성. NewNode는 이 노드의 주소를 가리킨다.
3. SLL_AppendNode()를 호출하면서 매개변수들 _Head와 _NewNode가 자동 메모리에 생성되고 List는 _Head에 NewNode는 _NewNode에 메모리의 주소를 복사해서 넣는다.
4. List포인터가 담고 있는 주솟값만 복사되고 List포인터 변수의 주소는 전달되지않는다.
5. 함수 실행 전과 마찬가지로 List는 NULL로 남는다.

노드 탐색

배열은 인덱스를 통해 원하는 element에 바로 접근할 수 있으나 연결 리스트는 헤드부터 시작해서 노드들을 순차적으로 하나하나 건너와야 접근이 가능하다.

Node *SLL_GetNode(Node *Head,int Location) {
  Node *Current = Head;
  while (Current != NULL && (--Location) >= 0)
    Current = Current->NextNode;
  return Current;
}

Location이 0이 될때까지 노드를 순차적으로 이동한다.
이렇게 바로 접근이 불가능한 것은 연결 리스트의 단점으로 볼 수 있다.

노드 삭제

void SLL_RemoveNode(Node **Head, Node *Remove) {
  if (*Head == Remove) *Head = Remove->NextNode;
  else {
    Node *Current = *Head;
    while (Current != NULL && Current->NextNode != Remove) 
      Current = Current->NextNode;
    if (Current != NULL) 
      Current->NextNode = Remove->NextNode;
  }
}

삭제하고자 하는 노드를 찾고 해당 노드의 다음 노드를 이전 노드의 NextNode에 연결하면 노드를 삭제할 수 있다.

노드 삽입

노드와 노드 사이에 새로운 노드를 끼워넣는다.
이전 노드의 NextNode포인터가 새 노드를 가리키고 새 노드의 NextNode포인터가 다음 노드를 가리키게 하면 될 것이다.

void SLL_InsertAfter(Node *Current,Node *NewNode) {
  NewNode->NextNode = Current->NextNode;
}

와 같이 쉽게 구현된다.

노드 개수 세기

int SLL_GetNodeCount(Node *Head) {
  int Count = 0;
  Node *Current = Head;
  while (Current != NULL) {
    Current = Current->NextNode;
    Count++;
  }
  return Count;
}

그냥 끝까지 도달할 때까지 카운트 수를 늘려주면 된다.

3. 이중 연결 리스트 (double linked list)

• 단일 연결 리스트: head에서 tail로만 탐색 가능

• 이중 연결 리스트: 양방향 탐색 가능

• 노드 구조: 포인터가 데이터의 앞뒤로 모두 존재함

typedef int ElementType;

typedef struct tagNode {
  ElementType Data;
  struct tagnode *PrevNode;
  struct tagNode *NextNode;
} Node;

단일 연결 리스트와 다르게 PrevNode포인터가 추가되었다.

노드 생성/소멸

Node *DLL_CreateNode(ElementType NewData) {
  Node *NewNode = (Node*)malloc(sizeof(Node));
  NewNode->Data = NewData;
  NewNode->PrevNode = NULL;
  NewNode->NextNode = NULL;
  return NewNode;
}
void DLL_DestroyNode(Node *Node) {
  free(Node);
}

단일 연결 리스트와 크게 다를 것이 없으나 PrevNode관련만 추가되었다. 노드 삭제는 동일하다.

노드 추가

void DLL_AppedNode(Node **Head, Node *NewNode) {
  if ((*Head) == NULL) *Head = NewNode;
  else {
    Node *Tail = (*Head);
    while (Tail->NextNode != NULL) Tail = Tail->NextNode;
    Tail->NextNode = NewNode;
    NewNode->PrevNode = Tail;
  }
}

기본적인 연산은 단일 연결리스트와 유사하나 새로운 노드의 PrevNode가 기존의 tail(끝)을 가리키도록 한다.

노드 삭제

이중 연결 리스트에서 노드 삭제는 다른 연산들보다 약간 복잡하다.

삭제할 노드의 포인터가 앞뒤 노드를 모두 가리키고 있으므로 노드의 양쪽 포인터, 앞 노드의 NextNode포인터 뒤 노드의 PrevNode포인터 모두를 건드려야한다.

void DLL_DeleteNode(Node **Head, Node *Remove) {
  if (*Head == Remove) {
    *Head = Remove->NextNode;
    if ((*Head) != NULL) ((*Head)->PrevNode = NULL);
    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
  else {
    Node *Temp = Remove;
    if (Remove->PrevNode != NULL)
      Remove->PrevNode->NextNode = Temp->NextNode;

    if (Remove->NextNode != NULL) 
      Remove->NextNode->PrevNode = Temp->PrevNode;

    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
}

노드 삽입

void DLL_InsertAfter(Node *Current, Node *NewNode) {
  NewNode->NextNode = Current->NextNode;
  NewNode->PrevNode = Current;
  if (Current->NewNode != NULL) {
    Current->NextNode->PrevNode = NewNode;
    Current->NextNode = NewNode;
  }
}

PrevNode로 이전 노드를, NextNode로 다음 노드를 가리키게 구성하면 된다. 삭제보다는 간단하다.

4. 환형 연결 리스트

일반적인 연결리스트와 크게 다르지는 않으나 그저 헤드가 테일과 연결되어있는 형태이다.

void CDLL_RemoveNode(Node **Head, Node *Remove) {
  if (*Head == Remove) {
    (*Head)->PrevNode->NextNode = Remove->NextNode;
    (*Head)->NextNode->PrevNode = Remove->PrevNode;
    *Head = Remove->NextNode;
    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
  else {
    Remove->PrevNode->NextNode = Remove->NextNode;
    Remove->NextNode->PrevNode = Remove->PrevNode;
    Remove->PrevNode = NULL;
    Remove->Nextnode = NULL;
  }
}

void CDLL_AppendNode(Node **Head, Node *NewNode) {
  if ((*Head) == NULL) {
    *Head = NewNode;
    (*Head)->NextNode = *Head;
    (*Head)->PrevNode = *Head;
  }
  else {
    Node *Tail = (*Head)->PrevNode;
    Tail->NextNode->PrevNode = NewNode;
    Tail->NextNode = NewNode;
    NewNode->NextNode = (*Head);
    NewNode->PrevNode = Tail;
  }
}

연산이 크게 다를 것은 없고 헤드와 테일이 어떤 끝이 아니라 노드를 추가할 때도 헤드와 테일 사이에 삽입하는 느낌으로 접근하면 된다.