[C / C++] Singly Linked List 구현

Singly Linked List

배열처럼 데이터 집합을 보관하는 기능을 가지면서 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조인 Linked List 중, 단 방향으로 존재하며 가장 간단한 Linked List. 각 요소는 노드라 불리는 각 단위에 저장.


Singly Linked List의 주요 연산

  • 노드 생성/소멸
  • 노드 추가
  • 노드 탐색
  • 노드 삭제
  • 노드 삽입

노드 구현

1
2
3
4
5
typedef struct Node
{
  int Data;
  struct Node* NextNode;
} Node;
cs

typedef는 특정한 이름으로 type을 명시하기 위한 방법. typedef로 명시하지 않으면 Node 구조체를 불러올 때마다 struct 키워드를 동반하여 “struct Node”로 불러야 합니다. 아래와 같이 정의할 수 있으며, OldType과 NewType이 위와 같이 같아도 무방합니다.

typedef OldTypeName NewTypeName;

노드 생성

1
2
3
4
5
6
7
8
Node* SSL_createNode(int newData)
{
 Node* newNode = (Node*)malloc(sizeof(Node)); //malloc으로 자유 저장소에 메모리를 할당한 후, 주소값을 Return해야 함수를 호출한 쪽에서 정확한 값을 받을 수 있다.
 newNode>data = newData;
 newNode>nextNode = NULL;
  return newNode;
}
cs

malloc을 이용하지 않고, Node newNode; 와 같이 지역 변수가 저장되는 자동 메모리에 변수를 할당할 경우, return으로 값을 넘겨준 후 SSL_createNode 함수 종료와 함께 메모리에서 제거됩니다.

아래와 같이 main함수에서 구현할 수 있습니다.

Node* myNode = SSL_createNode(10);

노드 소멸

1
2
3
4
void SLL_destroyNode(Node* Node)
{
  free(Node);
}
cs

free 함수에 주소값을 넣는 것만으로 쉽게 소멸시킬 수 있습니다. #include <stdlib.h>가 꼭 동반되어야 사용할 수 있는 함수입니다.


노드 추가

Linked List의 꼬리 부분에 새로운 노드를 추가(Append)하는 연산

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SSL_appendNode(Node** head, Node* newNode)
{
  if(*head == NULL)
 {
  *head = newNode;
 }
  else
 {
 Node* tail = *head;
  while(tail>nextNode != NULL)
 {
 tail = tail>nextNode;
 }
 tail>nextNode = newNode;
 }
}
cs

아래 main함수에 작성된 코드를 보면, SSL과 newNode에 모두 NULL값을 할당했습니다. 즉, 새로운 노드 추가 시, head 노드 부분이 NULL이면, newNode가 head가 되고 그렇지 않을 시, 꼬리 노드를 찾아 꼬리 노드와 연결합니다.

1
2
3
4
5
 Node* SSL = NULL;
 Node* newNode = NULL;
 newNode = SSL_createNode(10);
 SSL_appendNode(&SSL, newNode);
cs

&SSL, 즉, Node* 자료형의 주소 값을 전달하고, SSL_appendNode함수에서 Node**형으로 받는 이유는 자동 메모리와 자유 저장소와 관련 있습니다. 만약, Node*형으로 전달하게 되면 SSL_appendNote함수를 호출했을 때, SSL이 담고 있는 “주소 값”만 전달되고, SSL 포인터 변수의 주소 자체는 전달되지 않아, 함수가 종료되더라도 SSL은 NULL을 유지하게 됩니다.


노드 탐색

head부터 시작하여 차근차근 노드를 건너 뛰어 가며 원하는 요소를 찾아내는 연산.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Node* SSL_getNodeAt(Node* head, int index)
{
 Node* current = head;
  while(current != NULL && index >= 0)
 {
 current = current>nextNode;
 }
  return current;
}
int main(int argc, const char * argv[])
{
 Node* SSL = NULL;
 Node* newNode = NULL;
 newNode = SSL_createNode(10);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(20);
 SSL_appendNode(&SSL, newNode);
 Node* searchedNode = SSL_getNodeAt(SSL, 1);
  printf(“%d\n”,searchedNode>data); //결과값 20
}
cs

매개변수로 넘겨받은 index값을 1씩 감소시키며 0까지 while문을 돌리며, 다음 노드로 이동합니다.


노드 삭제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void SSL_removeNode(Node** head, Node* removedNode)
{
  if(*head == removedNode)
 {
  *head = removedNode>nextNode;
 }
  else
 {
 Node* current = *head;
  while(current != NULL && current>nextNode != removedNode)
 {
 current = current>nextNode;
 }
  if(current != NULL)
 current>nextNode = removedNode>nextNode;
 }
}
int main(int argc, const char * argv[])
{
 Node* SSL = NULL;
 Node* newNode = NULL;
 Node* searchedNode = NULL;
 newNode = SSL_createNode(10);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(20);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(30);
 SSL_appendNode(&SSL, newNode);
 searchedNode = SSL_getNodeAt(SSL, 1);
 SSL_removeNode(&SSL, searchedNode);
 SLL_destroyNode(searchedNode);
}
cs

삭제하고자 하는 노드를 찾아 삭제하는 코드.


노드 삽입

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void SSL_insertAfter(Node* current, Node* newNode)
{
 newNode>nextNode = current>nextNode;
 current>nextNode = newNode;
}
int main(int argc, const char * argv[])
{
 Node* SSL = NULL;
 Node* newNode = NULL;
 Node* searchedNode = NULL;
 newNode = SSL_createNode(10);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(20);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(30);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(25);
 searchedNode = SSL_getNodeAt(SSL, 1);
 SSL_insertAfter(searchedNode, newNode);
 SSL_display(&SSL);
}
cs

지정된 노드 이후에 새로운 노드를 삽입하는 연산.

PRINT CURRENT NODES
===================
10 20 25 30 
===================

C로 구현된 Singly Linked List 전체 코드

전체 구현된 코드 참조 바랍니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
  int data;
  struct Node* nextNode;
} Node;
Node* SSL_createNode(int newData)
{
 Node* newNode = (Node*)malloc(sizeof(Node)); //malloc으로 자유 저장소에 메모리를 할당한 후, 주소값을 Return해야 함수를 호출한 쪽에서 정확한 값을 받을 수 있다.
 newNode>data = newData;
 newNode>nextNode = NULL;
  return newNode;
}
void SLL_destroyNode(Node* Node)
{
  free(Node);
}
void SSL_appendNode(Node** head, Node* newNode)
{
  if(*head == NULL)
 {
  *head = newNode;
 }
  else
 {
 Node* tail = *head;
  while(tail>nextNode != NULL)
 {
 tail = tail>nextNode;
 }
 tail>nextNode = newNode;
 }
}
Node* SSL_getNodeAt(Node* head, int index)
{
 Node* current = head;
  while(current != NULL && index >= 0)
 {
 current = current>nextNode;
 }
  return current;
}
void SSL_removeNode(Node** head, Node* removedNode)
{
  if(*head == removedNode)
 {
  *head = removedNode>nextNode;
 }
  else
 {
 Node* current = *head;
  while(current != NULL && current>nextNode != removedNode)
 {
 current = current>nextNode;
 }
  if(current != NULL)
 current>nextNode = removedNode>nextNode;
 }
}
void SSL_insertAfter(Node* current, Node* newNode)
{
 newNode>nextNode = current>nextNode;
 current>nextNode = newNode;
}
void SSL_display(Node** head)
{
 Node* current = *head;
  printf(“PRINT CURRENT NODES\n”);
  printf(“===================\n”);
  while(current != NULL)
 {
  printf(“%d\t”,current>data);
 current = current>nextNode;
 }
  printf(“\n===================\n\n”);
}
int main(int argc, const char * argv[])
{
 Node* SSL = NULL;
 Node* newNode = NULL;
 Node* searchedNode = NULL;
 newNode = SSL_createNode(10);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(20);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(30);
 SSL_appendNode(&SSL, newNode);
 newNode = SSL_createNode(25);
 searchedNode = SSL_getNodeAt(SSL, 1);
 SSL_insertAfter(searchedNode, newNode);
 SSL_display(&SSL);
}
cs

C++로 구현한 Singly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//
//  main.cpp
//  c++
//
//  Created by Travelholics on 09/03/2018.
//  Copyright © 2018 None. All rights reserved.
//
#include <iostream>
using namespace std;
typedef struct Node
{
  int data;
  struct Node* nextNode;
} Node;
class SSL
{
  private:
 Node *head, *tail;
  public:
 SSL()
 {
 head = NULL;
 tail = NULL;
 }
  //create node
  void createNode(int data)
 {
 Node *newNode = new Node;
 newNode>data = data;
 newNode>nextNode = NULL;
  if(head == NULL)
 {
 head = newNode;
 tail = newNode;
 }
  else
 {
 tail>nextNode = newNode;
 tail = newNode;
 }
 }
  //destroy node
  void destroyNode(Node *removedNode)
 {
  delete removedNode;
 }
  //get node
 Node* getNodeAt(int index)
 {
 Node* current = head;
  if(current != NULL && index>=0)
 {
 current = current>nextNode;
 }
  return current;
 }
  //delete node
  void deleteNode(Node *deletedNode)
 {
  if(head == deletedNode)
 {
 head = head>nextNode;
 }
  else
 {
 Node* current = head;
  while(current != NULL && current>nextNode != deletedNode)
 {
 current = current>nextNode;
 }
 current>nextNode = deletedNode>nextNode;
 }
 destroyNode(deletedNode);
 }
  //show node
  void showNode()
 {
 Node *current = head;
  cout<<“PRINT CURRNET NODES”<<endl;
  cout<<“===================”<<endl;
  while(current != NULL)
 {
  cout << current>data << “\t”;
 current = current>nextNode;
 }
  cout<<endl<<“===================”<<endl;
 }
};
int main(int argc, const char * argv[]) {
 SSL ssl;
 ssl.createNode(3);
 ssl.createNode(4);
 ssl.createNode(5);
 ssl.deleteNode(ssl.getNodeAt(1));
 ssl.showNode();
}
cs

참조

댓글 남기기