[Data Structure] 연결 리스트(Linked List)

지난번에 선형 리스트에 대해서 소개를 했습니다. 그러나 선형 리스트는 배열이기 때문에 크기가 정해져있다는 큰 문제점을 가지고 있었습니다. 이점을 보완한 구조가 연결 리스트입니다.

---

1. 연결 리스트

연결 리스트는 노드로 이루어진 리스트 입니다. 선형 리스트와 다르게 자료의 물리적 순서와 논리적인 순서가 일치하지 않아도 된다는 점이 있으며, 각 자료들은 노드를 통해 저장되고 연결되어있습니다.

연결 리스트는 단순, 원형, 이중 연결과 같은 여러 방식이 있으며 여러 포스트에 걸쳐서 차차 소개해나가도록 하겠습니다.

 

 

2. 노드의 구조

리스트 첫 시간에도 설명했지만 노드는 다음과 같은 구조를 가지고 있습니다.

링크 필드가 다음 노드를 가리키고 있고 이것들이 이어져서 리스트를 구성하는 방식이었죠. 이러한 노드를 구현해보면 다음과 같습니다.

class Node<E> {
	E data;
	Node<E> next;
}

우선 제네릭 형태로 구현했기 때문에 E에는 data 변수에 담길 데이터의 자료형을 지정하면 됩니다. 그리고 다음 노드를 가리키는 next 변수는 자기 자신과 같은 Node<E> 클래스를 담을 수 있습니다.

---

연결 리스트의 첫 포스트는 간단히 소개만 하고 넘어갑니다. 그리고 다음 포스트 부터 연결 리스트 종류의 소개와 간단한 구현 위주로 풀어나가겠습니다.