-연결리스트는 (데이터와 다음 노드의 주소를 담고 있는) 노드들이 한 줄로 연결되어 있는 방식의 자료구조이다.
-연결되는 방향에 따라 singly linked list(단일 연결 리스트), doubly linked list(이중 연결 리스트), circular linked list(환형 연결 리스트)가 있다.

Linked list란?

Linked List는 데이터를 노드의 형태로 저장한다. 노드에는 데이터와 다음 노드를 가리키는 포인터를 담은 구조로 이루어져 있다.

Linked list는 Array 처럼 선형 데이터 자료구조이지만, Array는 물리적인 배치 구조 자체가 연속적으로 저장되어 있고 Linked list는 위의 노드의 Next 부분에 다음 노드의 위치를 저장함으로써 선형적인 데이터 자료구조를 가진다.

🔥Linked list의 장점과 단점

★Liked list의 장점
(1) Linked list의 길이를 동적으로 조절 가능하다.
(2) 데이터의 삽입과 삭제가 용이하다.

☆Linked list의 단점
(1) 임의의 노드에 바로 접근할 수가 없다.
(2) 다음 노드의 위치를 저장하기 위한 추가 공간이 필요하다.
(3) Cache locality를 활용해 근접 데이터를 사전에 캐시에 저장하기가 어렵다.
(4) Linked list를 거꾸로 탐색하기가 어렵다.

✔cache locality: 대부분 프로그램은 한번 사용한 데이터를 다시 사용할 가능성이 높고, 그 주변의 데이터도 곧 사용할 가능성이 높은 데이터 지역성을 가지고 있다. 데이터 지역성을 활용하여 메인 메모리에 있는 데이터를 캐시 메모리에 불러와 두고, CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하면 시스템 성능을 향상시킬 수 있다.

단일 연결 리스트 구현하기

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간(다음 노드의 주소를 담는 공간)이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

📌삽입

📌삭제

이중 연결 리스트 구현하기

Doubly linked list는 각 노드에 자료 공간과 두 개의 포인터 공간이 있고, 각 노드의 포인터는 이전 노드와 다음 노드를 가리킨다.

📣 이중 연결 리스트의 특징, 장점, 단점

단순 연결리스트와 이중 연결 리스트의 차이는 prev를 가리키는 포인터 공간이 추가되면서 이전노드에 대한 정보를 알 수 있다는 점이다. 이로인해 단순 연결 리스트로는 할 수 없는 역으로 출력하는 것이 가능하고, 특정 노드의 이전 노드를 삭제하거나 특정 노드의 이전에 삽입하는게 가능해졌다. 그러나 단순 연결 리스트 자료구조 만으로도 기능이 충분하다면 포인터 공간을 추가하여 메모리 공간을 낭비하지 않는게 좋다.

📌삽입

📌삭제

환형 연결 리스트 구현하기

Circular linked list라 부르는 이 연결 리스트는 머리와 꼬리가 연결되어 순환 구조를 지닌다. 환형 연결 리스트라는 것은 Node에 포인터 공간이 두 개 일수도 있고, 한 개 일수도 있으며 포인터 공간의 개수가 중요한 것이 아니라 노드의 Next가 None인 경우가 없이 끊임 없이 이어진다는 의미이다. 따라서 노드가 한개인 경우에도 무한대로 순환할 수 있다.

📌삽입

📌삭제

Runner 기법

Runner(부가 포인터라고도 한다)는 연결리스트 문제에서 많이 활용되는 기법이다. 연결리스트를 순회할 때 두개의 포인터를 동시에 사용하는 것이다. 이때 한 포인터가 다른 포인터보다 앞서도록 한다. 앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼을 앞서도록 할 수도 있고, 아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있다.

재귀 문제

연결리스트 관련 문제 가운데 상당수는 재귀 호출에 의존한다. 연결리스트 문제를 푸는 데 어려움을 겪고 있다면, 재귀적 접근법은 통할지 확인해 봐야 한다.
하지만 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n) 만큼의 공간을 사용한다는 사실을 기억하자. 모든 재귀(recursive) 알고리즘은 반복적(iterative) 형태로도 구현될 수 있긴 하지만 반복적 형태로 구현하면 한층 복잡해질 수 있다.