연결리스트는 여러 개의 열차들이 연결되어 있는 것과 같다.

Linked List 연결리스트

데이터를 포함하는 노드들을 연결식으로 만든 자료구조
데이터와 다른 데이터를 가리키는 참조변수를 가진 노드를 기본 단위로 사용
데이터를 노드를 통해 연결식으로 구성하기 때문에 데이터의 추가/삭제에 유용
노드가 메모리에 연속적으로 배치되지 않고 연결 구조로 다른 데이터의 위치를 확인

연결리스트 구현

연결리스트는 노드를 기본 단위로 연결식으로 구현되어 있다.
노드 간의 연결 구조에 따라 단방향, 양방향, 환형이 있다.

1. 단방향 연결리스트

노드가 다음 노드를 참조

2. 양방향 연결리스트

노드가 이전/다음 노드를 참조

3. 환형 연결리스트

노드가 이전/다음 노드를 참조하며, 시작 노드와 마지막 노드를 참조

연결리스트 삽입

새로 추가하는 노드가 이전/이후 노드를 참조하게 한 뒤
이전/이후 노드가 새로 추가하는 노드를 참조함

연결리스트 삭제

삭제하는 노드의 이전 노드가 이후 노드를 참조한 뒤
삭제하는 노드의 이후 노드가 이전 노드를 참조함

연결리스트 특징

연결리스트의 경우 데이터를 연속적으로 배치하는 배열과 다르게 연결식으로 구성
-> 데이터의 추가/삭제 과정에서 다른 데이터의 위치와 무관하게 진행되므로 수월함
하지만 데이터의 접근 과정에서 연속적인 데이터 배치가 아니기 때문에 인덱스 사용이 불가하여 처음부터 탐색해야함

시간복잡도

접근 : O(n)
탐색 : O(n)
삽입 : O(1)
삭제 : O(1)

리스트와 연결리스트

리스트와 연결리스트는 이름이 비슷하고 선형적이라는 점에서 비슷하지만 구현된 성질은 다르다.

리스트는 삽입과 삭제 시 배열을 당기거나 미는 등 비효율적이게 된다.
그리고 배열의 크기 예측이 어려울 때는 마찬가지로 메모리의 낭비가 일어날 수 있다.

반면 연결리스트는 빈 메모리 공간 아무 곳에 데이터를 생성하고 연결해줄 수 있기에 크기를 정할 필요가 없다.
삽입과 삭제 시 포인터가 어디를 가리키게 할지만 변경하게 되기 때문에 삽입, 삭제 시 훨씬 효율적이다.

또 다른 점은 캐시 적중률에 있는데, 캐싱을 할 때 인접한 데이터를 함께 캐싱을 하기 때문에 메모리 상에서 연속적으로 존재하는 리스트가 캐싱 면목에서 더 효율적이다.