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

|  요약

종류	구분	내용	언제 쓰는 게 좋을까
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부터 타겟지점까지 모두 순회해야 하기 때문이다.

	add()	remove()	get()	contains()
ArrayList	O(1) or O(n)	O(1) or O(n)	O(1)	O(n)
LinkedList	O(1)	O(1)	O(n)	O(n)

 

|  연결리스트와 큐, 데크

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

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

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

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

 

|  연결리스트 문제집

https://www.acmicpc.net/workbook/view/1066

문제집: Linked List (DryType)

 

 

[ 참고 ] 

https://hbase.tistory.com/185

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8