자료구조, 그 두 번째 이야기 | 연결 리스트

 지금까지 자주 사용하던 배열은 다음과 같은 특징이 있다.

 - 상수 시간에 임의의 위치에 접근할 수 있다. (연산 한 번으로 arr[100] 등에 들어있는 값을 찾을 수 있다)

하지만 배열의 어떤 위치에 특정 값을 삽입하려면 그 뒤에 있는 모든 수를 한칸씩 밀어주어야 하므로 시간이 오래 걸린다. 예를 들어 다음과 같이 새로운 값을 넣어주려면

이렇게 삽입되는 위치의 뒤에 있는 모든 수를 한 칸씩 밀어 주어야 한다.

하지만 이렇게 배열처럼 일렬로 늘어서 있는 구조가 아니라 서로  화살표로 이어져 있는 구조라면?

새로운 값을 넣을 때 바로 앞과 뒤의 화살표 방향만 바꾸어 주면 새로운 값을 넣을 수 있게 된다.

이렇게 다음 자료의 위치(포인터)를 저장하는 방식을 연결리스트라고 한다. 

그러면 이제부터 구현을 보자.

먼저 각각의 노드를 정의하자.

struct node{
	node *nex=NULL;
	int gap=0;
};

여기에서 node 안에 node가 선언되어 있는 것이 오류를 일으킬 것 같지만, node형 변수를 선언한 것이 아니라 그 포인터를 선언한 것이므로 컴파일 오류가 일어나지 않는다.

그리고 연결리스트의 맨 처음 노드를 뜻하는 root를 선언해주자.

node *root=new node;

pre가 가르키는 노드 뒤에 새 원소를 추가하는 것은 다음과 같이 구현할 수 있다.

void push(node *pre, int in)
{
	node *now=new node;
	now->gap=in;
	now->nex=pre->nex;
	pre->nex=now;
}

또한 pre가 가르키는 노드 뒤의 원소를 제거하는 것은 다음과 같이 구현할 수 있다. (주의하자. pre를 삭제하는 것이 아니다)

void push(node *pre, int in)
{
	node *now=new node;
	now->gap=in;
	now->nex=pre->nex;
	pre->nex=now;
}

마지막으로 ind번째 원소의 값은 다음과 같이 참조할 수 있다. (번호는 root를 제외하고 센다)

int ref(int ind)
{
	node *now=root;
	while(ind--)
		now=now->nex;
	return now->gap;
}

 

기본적인 연결리스트 외에도 여기에 살짝 변형을 준

이중 연결리스트 (화살표를 양방향으로 저장함)

원형 연결리스트 (처음과 끝이 연결됨)

등이 있다. 이것들은 위 구현에서 몇 줄만 변경해도 쉽게 구현할 수 있다.