[선형자료구조] 연결리스트

| 요약

종류	구분	내용	언제 쓰는 게 좋을까
LinkedList	특징	- 각 노드가 연결된 상태 - 각 노드의 메모리 주소는 항상 연속적이지 않다. - head / tail (양방향 이상)	- 자료의 삽입과 삭제가 많은 경우
	장점	- 데이터의 삽입 및 삭제가 잦을 때 유리 * 삽입, 삭제 시 새로운 배열 생성 없이 링크만 연결한다.
	단점	- 특정 인덱스를 조회하는 데 시간이 O(n)만큼 소요된다. * 처음~끝까지 인덱스를 돌기 때문에 Array보다 느리다.
	양방향	- 각 노드가 prev / next 두 가지의 연결점을 가진다.
	원형	- head -> tail -> head 식으로 원형으로 연결된 상태

- 연결리스트는 각 노드가 연결된 상태로, 삽입과 삭제가 용이하다.

- 다만, 연결리스트는 조회에는 취약한데 그 이유는 처음부터 노드를 순회해야 원하는 타켓을 조회할 수 있기 때문이다.

- 연결리스트는 기본적으로 각각의 노드가 데이터와 포인터를 가진 구조로 되어있다.

- 단방향 연결리스트는 아래와 그림과 같이 각 노드가 next 포인터를 통해 한 방향으로만 연결된 구조인데

이러한 구조에서는 head노드가 있고, tail은 없는 상태이다.

- 양방향 연결리스트는 아래의 두번째 그림과 같이 각 노드에 prev, next 포인터가 각각 있는 상태를 말한다.

이 구조에서는 head 노드도 있으며, tail 노드도 존재한다.

왜냐하면, 각각의 노드 뿐 아니라 전체적인 방향 자체가 양방향이기 때문에 tail이 필요하기 때문

- 원형 연결리스트는 tail 노드의 next가 head를 향하고 있는 상태로, 결과적으로 리스트를 순회하는 구조이다.

만약, 양방향 연결까지 더해준다면 시계방향, 반시계방향 모두로 순회가 가능하다.


단방향	양방향	원형

* 이미지 출처 : 위키 백과

- 연결리스트의 삽입과 삭제는 O(1) 의 시간 복잡도를 갖는다.

단순히 노드 사이에 연결만 이루어지면 되기 때문이다.

- 하지만 조회시에는 O(n)의 시간복잡도를 갖는다는 단점이 있다.

배열과 같이 인덱스가 있는 것이 아니라 노드의 head부터 타겟지점까지 모두 순회해야 하기 때문이다.

- 연결리스트는 큐와 구조적으로 동일하다고 볼 수 있는데, 이유는 큐와 마찬가지로 선입선출이 가능하기 때문이다.

- 자바에서는 Java.util 라이브러리의 LinkedList를 통해 연결리스트를 사용할 수 있으며, 단방향연결리스트만 제공한다.

- 만약, 양방향 연결리스트가 필요한 경우, Doubly-LinkedList를 별도로 구현하거나 단방향을 활용하는 게 필요하다.

- 만약, 원형 연결리스트가 필요하다면, Deque를 대안적으로 사용할 수 있다.

문제집: Linked List (DryType)

www.acmicpc.net

[ 참고 ]