연속되지 않은 메모리에 저장된 데이터들을 연결시켜 놓은 것.

배열과 완전히 대칭점에 서 있는 자료구조로, 순서가 있는 값들을 순서대로 보존하고 있습니다. 그러나 값 하나하나가 노드를 이루고 있으며, 각 노드는 자신의 다음 노드를 가리키고 있습니다. 만약 다음 노드가 없다면 포인터가 null 포인터 입니다.

연결리스트 성질

• k번째 원소를 확인/변경하기 위해 O(k)가 필요함
• 임의의 위치에 원소를 추가/제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움.

노드

• 자신이 보존 중인 값
• 다음 노드를 가리키는 포인터

연결 리스트의 노드 중 첫번째 값을 가지는 노드를 헤드 노드 라고 합니다.

insert

새로운 값을 어딘가 삽입하는 경우입니다.

두 번째 노드와 세 번째 노드 사이에 값 5를 삽입하려 합니다.

이때는 기존의 두 번째 노드가 새 노드를 가리키게 하고, 새 노드가 기존의 세 번째 노드를 가리키게 하면 됩니다.

delete

노드를 삭제하는 경우 3번째 노드를 삭제한다고 가정하면, 2번째 노드가 4번째 노드를 가리키게 하면 3번째 노드가 삭제 됩니다.

Big O Notation

헤드 포인터만 갖고 삽입 및 삭제 연산을 하려면 크리가 N일 때 O(N)의 시간이 걸립니다.