연결 리스트(Linked List) 개념 (1)

[ 구조체(C) 및 클래스(C++) 두가지 방식으로 구현하는 연결 리스트 ] 

배열의 특징

배열을 선언했다는 것은 순차접근이 가능하다는 것이 가장 큰 특징이다.

배열의 단점

그 크기가 고정(결정)되어있어야 한다.(즉, 크기가 가변적이지 않다.)

이렇듯이 배열은 순차적 접근이 가능하지만, 크기가 고정되어있고

메모리 할당을 통한 공간들은 순차적 접근이 불가능 하지만, 크기가 가변적이어서 서로 각각의 장단점이 존재한다.

따라서 배열이 좋은 면도 있지만 공간을 가변 시키기 위해서는 연결 리스트를 공부하여

공간을 늘렸다 지웠다가를 유연해지도록 하는 것을 배우는 것도 좋은 방법이다.

연결 리스트를 배우기 위해 처음 알아야 될 것은 node이다.

node라는 것은 새로운 type이 아닌 구조체/클래스 내부에 구현하는 것이다.

구조체에서의 구현은 다음과 같다.

typedef struct Node
{
 
 int data;   // 데이터를 담을 공간
 Node *next; // 연결의 도구
 
}node;
 

클래스에서의 구현은 다음과 같다.

class node
{
 
 private:
     int data;   // 데이터를 담을 공간
     node *next; // 연결의 도구
 
}; // public로 하면 조금 더 편하지만, 코드의 보안을 높이기 위해서는 private를 이용하는것을 습관화 한다.
 

구조체/클래스에서 node *next;의 의미는

type이 node인 포인터이므로 구조체/클래스를 가리킬 수 있게된다.

이때 int *next는 왜안되나??

int는 type이 node와 다르므로 구조체/클래스를 가리킬 수 없다.

즉, 같은 type끼리 포인터를 이용할 수 있다는 것이다.

그리고 선언 안에 다시 선언이 되는가를 의문점으로 가질 수 있지만, 이것은 그대로 받아 들이는 것으로 한다.

(즉, 구조체/클래스 node를 선언하였는데 그 속에 node를 바로 이용하는 것을 그대로 받아 들인다.)