연결리스트란?
스택과 큐 등의 자료구조를 배열을 이용하여 구현하면 구현이 간단하고 빠르다는 장점이 있지만 크기가 고정된다는 단점이 있다.
즉, 배열은 처음에 설정한 공간이 가득 차면 더 이상 데이터를 추가할 수 없다.
연결된 표현(linked representation)을 사용하면 이러한 문제를 해결할 수 있다.
연결된 표현은 데이터와 링크로 구성되어있고 링크가 노드들을 연결하는 역할을 한다.
연결된 표현의 특징
- 데이터를 한군데 모아두는 것을 포기한다.
- 데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다.
- 순서를 유지하기 위해 각각의 데이터는 다음 데이터를 가리키는 줄을 가진다.
- 첫 데이터에서부터 순서대로 줄을 따라가면 모든 데이터를 방문할 수 있다.
이와 같이 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트(linked list)라고 한다.
일반적으로 자료들을 연결하는 줄을 포인터로 구현한다. 포인터를 사용하면 하나의 자료에서 다음 자료로 쉽게 이동할 수 있다.
연결리스트는 배열과 대응되는 의미로 다음과 같은 장점들이 있다.
- 크기가 고정되지 않는다.
- 중간에 자료를 삽입하는 것이 가능하며 용이하다.
- 중간에 있는 자료를 삭제하는 것이 가능하며 용이하다.
- 데이터 저장을 위한 메모리를 공간이 필요할 때마다 동적으로 만들어 쉽게 추가할 수 있다.
이러한 장점들이 있지만 구현이 어렵고 오류가 나기 쉽다는 단점이 있다.
연결 리스트의 구조
노드(Node)
위 그림의 상자를 노드라고 한다. 연결 리스트는 노드들의 집합이며 이들은 데이터를 저장하고 서로 연결되어 있다.
일반적인 노드는 데이터 필드(data field)와 링크 필드(link field)로 구성되어 있다.
데이터 필드에는 우리가 저장하고 싶은 자료가 저장되고, 링크 필드에는 다른 노드의 주소를 저장하는 포인터 변수가 저장된다.
→ 링크 필드의 주소를 통해 현재 노드에 연결된 다음 노드를 알 수 있다.
헤드 포인터(Head Pointer)
연결 리스트는 첫 번 째 노드를 알면 링크로 연결되 있는 전체 노드에 모두 접근할 수 있다. 따라서 연결리스트에서는 첫 번째 노드를 가리키는 포인터가 필요한데 이 포인터를 헤드 포인터라고 한다.
연결리스트의 마지막 노드는 더 이상 연결할 노드가 없는데, 링크 필드 값을 NULL로 설정함으로서 이 노드가 마지막 노드임을 표현한다.
연결 리스트의 종류
연결 리스트에는 세가지 종류가 있다.
첫 번째로 단순 연결 리스트(singly linked list)는 하나의 방향으로만 연결되어 있으며,
마지막 노드의 링크 필드는 NULL 값을 가진다.
두 번째로 원형 연결 리스트(circular linked list)는 단순 연결 리스트와 같지만 마지막 노드의 링크 값이 다시 첫 번째 노드를 가리킨다.
마지막으로 이중 연결 리스트(doubly linked list)는 각 노드마다 링크 필드가 2개씩 존재하며 각각의 노드는 선행 노드와 후속 노드를 모두 가리킬 수 있다.
연결리스트로 구현한 스택의 구조
배열을 이용한 스택과는 다르게 연결된 스택에서는 각 요소들을 한거번에 할당하지 않고 필요할 때마다 하나씩 동적으로 할당한다. 연결된 스택에서는 스택에 저장할 요소(데이터 필드)와 함께 다음 노드를 가리키기 위한 포인터(링크 필드)를 데이터 멤버로 가지는 노드 클래스를 추가로 정의한다.
배열로 구현된 스택에서 배열의 인덱스를 나타내던 top은 이제 포인터 변수가 되야한다.
→ 배열로 구현된 스택에서의 top이 연결 리스트로 구현된 스택에서는 헤드 포인터이다.
마지막 노드의 링크 필드는 마지막임을 나타내기 위해 값이 NULL이 된다.
연결된 스택의 동작
삽입 연산
(1) 노드 D의 링크 필드가 노드 C를 가리키도록 한다. p->link = top;
(2) 헤드 포인트 top이 노드 D를 가리키도록 한다. top = p;
삭제 연산
(1) 포인터 변수 p 가 노드 C를 가리키도록 한다. p = top;
(2) 헤드 포인터가 노드 B를 가리키도록 한다. top = p->Next; == top = top->link;
(3) 포인터 p를 반환 한다. return p;
연결된 스택에서의 공백상태는 헤드 포인터 top의 값이 NULL일 경우이다.
포화 상태는 동적 메모리 할당을 하기 때문에 없는 것이나 마찬가지다.
연결 리스트로 구현한 큐의 구조
스택과 마찬가지로 큐도 연결리스트를 이용해 구현할 수 있다.
연결된 큐도 메모리 공간에서 물리적으로 흩어져 있는 노드들로 이루어진다. 원형 큐에서 front와 rear가 배열의 인덱스를 나타내는 반면에 연결된 큐에서는 이들은 포인터 변수가 된다. front는 큐에 가장 먼저 삽입된 노드를, rear는 가장 최근에 삽입된 노드를 가리킨다.
각 노드들은 다음 노드를 가리키는 링크 필드를 가지며, 마지막 노트의 링크 필드는 NULL이 되어 더 이상 연결된 요소가 없음을 나타낸다.
연결된 큐의 연산
삽입 연산
연결된 큐가 공백 상태일 경우
연결된 큐가 공백 상태가 아닐 경우
1) rear가 가리키는 노드 C가 노드 temp를 가리키도록한다. rear->link = temp;
(2) rear가 이제 노드 p를 가이키도록 한다. rear = temp;
삭제 연산
노드가 둘 이상인 연결된 큐에서의 삭제 연산
노드가 하나 있는 연결된 큐에서의 삭제 연산
(1) front가 가리키는 노드A를 temp가 가리키도록 한다. temp = front;
(2) front가 다음 노드 B를 가리키도록한다. front = temp->link;
만약 노드가 하나뿐이면 rear도 NULL로 만들어 주어야 한다.
