잠보

연결리스트란?

연결리스트란 여러개의 노드를 연결함으로써 데이터를 보관하는 자료구조로 노드는 데이터를 가진 data 부분과 다음 노드를 연결하는 

link 부분으로 나뉘어져 있다.

연결리스트의 장점

1. 배열과는 다르게 필요한 만큼 메모리를 동적으로 할당 받아서 사용한다. 즉, 데이터 삽입 시에만 메모리 추가 사용하므로 효율적.
2. 삽입 삭제가 간단하다 : 새로운 노드 삽입 삭제 시 포인터 값(link)만 변경해주면 되기 때문이다.

연결리스트의 단점

1. 노드 접근이 배열보다 오래 걸린다 : 첫 노드부터 순차적으로 접근해야하기 때문이다. 메모리 구조상 차이.
2. 물리적으로 인접한 메모리에 위치해있지 않다 : 배열과 달리 포인터로 다음 노드의 위치를 알 수 있으므로 메모리 주소 공간이 떨어져있다.
3. 참조 포인터를 위한 메모리 공간이 낭비된다.

연결리스트의 시간복잡도

※ 중간 삭제 삽입 시 해당 위치의 전과 후의 데이터에 접근해야하고 작업을 해야하므로 O(n + 1)이 걸린다. 위의 삽입 삭제 상수시간은 접근을 고려하지 않고 삽입 삭제만 봤을 때의 시간이다.

연결리스트의 종류

1. 단일 연결리스트 : 가장 기본적인 연결리스트로 마지막 노드는 가리키는 노드가 없다. 보통 스택 구현에 많이 사용. 마지막 노드가 null을 가르킨다.
2. 이중 연결리스트 : 노드를 연결하는 link가 앞 뒤로 존재해서 앞 뒤 노드들 간의 관계를 바로 알 수 있다. 보통 큐 구현에 많이 사용. 단일 연결리스트는 헤드노드 유실시 전체 자료를 다 잃어버리지만 이중 연결리스트는 헤드만 아닌 테일 노드도 가지고 있으면 복구가 가능하다 또한 단일 연결리스트는 헤드에서만 탐색이 가능하나 이중 연결리스트는 테일에서도 탐색이 가능하므로 탐색의 방향이 바뀌어야 하는 경우 사용한다. 현실에서 사용하는 연결 리스트는 대부분 이중 연결리스트라고 보면 된다.
3. 원형 연결리스트 : 마지막 노드가 다시 처음 노드를 가리키는 연결리스트. 헤드와 테일의 구분이 없다. 스트림 버퍼의 구현에 많이 사용.

※ 물론 위의 연결리스트 구현될 수 있다는 스택, 큐 등 자료구조는 배열로도 큐를 단일 연결리스트로도 구현 가능하다 해당 자료구조만큼보다는 조금 비효율적이다라는 것이다.

배열과 연결리스트 사용 의문과 결론

동적배열과 연결리스트의 이 2개의 글을 읽어보셨으면 아시겠지만 결국 시간복잡도만 봤을 때 배열과 연결리스트는 데이터 접근과 탐색(탐색은 빅오 표기법은 같으나 메모리를 생각했을 때 조금의 차이)을 제외하면 별 다른 점이 없다. 

결국 자료구조의 설계를 기준으로 결정해야하는데 연결리스트는 마지막 노드에 한 해 데이터 추가 삭제 시 상수 시간이 걸리는 점을 생각 동적 배열은 마지막에 데이터를 추가 삭제 시 분할 상환할 경우에 상수 시간이 걸리다는 점과 데이터의 접근과 탐색을 생각하면 될 것 같다.

또한 보통 개발자가 배우기를 연결리스트는 삽입, 삭제에 유리, 배열은 접근 탐색에 유리하다는 것을 알고있다는 점도 반영.

결론은 데이터 접근, 탐색이 중요하면 배열을 사용. 데이터의 추가 삭제가 중요하면 연결리스트를 사용.

하지만 실무에서는 대부분 동적배열을 애용한다?!