[리스트: LIST] - 노드(Node)

단순한 배열의 한계

배열을 너무 작게 선언하면 오버플로우 걱정. 너무 크게 선언하자니 메모리 낭비...

이 두 문제를 해결 하기 위해 배열처럼 데이터 집합을 보관하는 기능을 가지면서도 한편으로는 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료 구조가 필요 하다. 이러한 문제를 해결 해 줄 수 있는 것이 바로 자료구조의 리스트이다.

 

리스트에는 스택과 큐, 트리를 이해 할 수 있는 가장 기초적인 기반이 된다. 그리고 메모리 처리 기법에 앞으로 익숙 해 질 수 있도록 해야한다.

 

 

노드 

우선 노드의 구조 부터 소개 하겠다. 왜냐하면 노드는 리스트를 구성하는 가장 기본적인 구성 요소 단위이기 때문이다. 그리고 큐, 스택, 트리 등의 자료구조에서도 가장 기본적인 구성 요소 단위로 사용되기 때문이다.

 

노드는 크게 2개의 영역으로 이루어 저 있다.

데이터가 보관되는 필드, 다른 노드와의 연결고리 역할을 하는 포인터 이다.

 

 

노드의 구조를 그림으로 표현하면 위의 사진과 같다.

 

 

 

앞에서 말했듯이 리스트 내의 각 요소는 노드(Node)라고 한다.

리스트는 위의 사진과 같이 노드가 어디에 있던지 포인터로 인해 다음 노드와 서로 연결 되어 있다.

 

 

 

좀 더 보기 쉽게 리스트의 모습을 정리해서 보면 다음과 같다.

그리고 시작 부분의 노드를 헤드(Head:머리) 마지막 부분의 노드를 테일(Tail:꼬리) 라고 부른다. 

이렇게 되면 데이터의 길이를 잘 몰라도 노드만 추가 해서 포인터로 연결 해 주기만 하면 된다.

삭제도 간단하다 노드의 포인터 연결을 끊어 주기만 하면 된다.

 

하지만 이러한 구조는 데이터를 찾아갈때 한쪽 방향으로밖에 갈 수 없다.

그렇기 때문에 이러한 구조의 노드를 단방향 노드라고 부르겠다.

 

단방향 노드를 c 언어 코드로 표현 하자면 구조체로 할 수 있다.

//typedef 키워드를 이용해서 Node 구조체를 정의하여 사용한 이유는
//이렇게 선언 한 Node 구조체는 간편하게 인스턴스를 만들어 사용하기 위해서다.
//Node MyNode; //<-- 이렇게 typedef 없이 간편하게 만들어 사용가능.

typedef struct tagNode
{
	int Data;	//데이터 영역
	struct tagNode* NextNode;	//포인터 영역
}Node;

 

 

단방향 노드의 문제를 해결 하기 위해서 노드에 포인터 영역을 하나 더 추가 한 구조를 가지도록 하면 해결 할 수 있다.

 

 

2개의 포인터와 데이터 영역을 가진 양방향 노드의 구조는 위의 사진과 같다.

 

 

 

이 노드 역시 위의 사진처럼 리스트로 나타 낼 수 있다.

화살표를 양방향으로 한 이유는 이전 노드와 다음 노드의 포인터 값을 알고 있기 때문에 양방향으로 표시 해 뒀다.

 

 

보기 쉽게 그리면 위의 사진과 같다.

 

양방향 노드를 c 언어 코드로 표현 하자면 구조체로 할 수 있다.

//typedef 키워드를 이용해서 Node 구조체를 정의하여 사용한 이유는
//이렇게 선언 한 Node 구조체는 간편하게 인스턴스를 만들어 사용하기 위해서다.
//Node MyNode; //<-- 이렇게 typedef 없이 간편하게 만들어 사용가능.

typedef struct tagNode
{
	int Data;	//데이터 영역
	struct tagNode* PrevNode;	//이전 노드를 가리키는 포인터 영역
	struct tagNode* NextNode;	//다음 노드를 가리키는 포인터 영역
}Node;

 

 

 

이렇게 여러개의 노드를 연결해서 만든 것이 '리스트' 이다. 앞으로 큐,스택, 트리 등에서도 계속 사용 되기 때문에 왠만하면 잘 알아두자.