[자료구조] 연결 리스트

 연결 리스트는 동적배열과 마찬가지로 배열의 단점을 보완하기 위해 만들어진 자료구조이다.

그렇다고해서 연결 리스트나 동적배열이 항상 배열 보다 좋다는 의미는 아니다. 

상황마다 장단점이 있기 때문에 자신의 필요에 따라 사용하면 된다.

C++에서는 STL 의 list , 자바에서는 LinkedList 로 표준 라이브러리에 구현되어 있다.

연결 리스트(Linked list) 란?

 연결 리스트란 자료구조의 각 부분부분인 노드들이 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드는 데이터를 담는 박스 같은 개념으로 생각하면 된다.

연결리스트는 택배박스를 생각하면 쉽다. 

물건(데이터)이 담긴 택배 박스(노드)를 보면 보낸 곳(이전 노드 포인터)과 보낼 곳(다음노드 포인터)이 쓰여 있다. 여기서 포인터는 현실에서 처럼 주소값을 의미한다.

연결 리스트는 각 노드에 이전과 다음 노드에 대한 포인터를 가지고 있어 배열과 다르게 메모리 여기저기에 노드들이 흩어져 있다.

연결 리스트가 필요한 이유

 

 연결 리스트는 노드들 사이에 데이터를 삽입하거나 삭제하는 작업이 많을 때 필요하다.

노드에 이전 데이터와 다음 데이터의 포인터를 가지고 있어서 삽입과 삭제 작업을 O(1)에 처리 할 수 있기 때문이다. ( 포인터만 바꿔주면 된다! )

만약 배열로 이러한 작업들을 하게 되면 평균적으로 데이터 개수에 선형 비례하는 시간이 소요되어 비효율 적이다. 배열에서는 중간에 데이터를 삽입하거나 삭제할 때 데이터들을 한칸 씩 옮겨야 해서 

시간복잡도가 O(n) 이다.

하지만 특정 위치의 데이터를 찾는 작업에서는 시간복잡도가 O(n) 이기 때문에 오히려 배열 보다 비효율 적이다. (배열은 데이터 검색 시 시간복잡도가 O(1) 이다. )

연결 리스트에서 데이터가 추가되는 경우

연결 리스트에서 데이터가 삭제되는 경우

연결 리스트의 종류

연결 리스트에는 대표적으로 3가지 종류가 있다.

1. 단일 연결 리스트

단일 연결 리스트는 각 노드에 데이터와 다음 노드를 가리키는 포인터가 담겨있다.

가장 단순한 형태의 연결 리스트다.

2. 이중 연결 리스트

이중 연결 리스트는 각 노드에 데이터와 이전 노드와 다음 노드의 포인터가 담겨있다.

단일 연결 리스트에서는 각 노드가 다음 노드는 알고 있으나 이전 노드를 알지 못해 이전 노드로 접근할 수가 없다. 이러한 단점을 보완하기 위해 이중 연결 리스트가 생겨났다.

3. 원형 연결 리스트

원형 연결 리스트는 단일 연결 리스트에서 마지막 노드와 처음의 노드를 연결시켜 원형 구조로 만든 것이다. 단인 연결 리스트는 임의의 노드 위치에서부터 이전에 위치한 노드에 접근할 수 없기 때문에 원형 구조를 만들어 순환해서 접근할 수 있도록 만든 것이다.