단순연결 리스트(singly linked list)

연결된 자료구조는 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 이 경우 서로 다른 메모리 위치에 데이터가 저장됩니다.

단순 연결리스트 기본 구조

이 그림과 같이 구성된 자료구조를 연결 리스트라고 합니다. 연결 리스트의 기본 구조에서 각각의 노드는 저장할 데이터와 다음 노드를 가리키는 포인터(next)를 가리키고 있습니다. 맨 마지막 노드에서는 다음 노드의 포인터 대신 자료구조의 끝을 나타내는 null을 가집니다. 

데이터 접근 시 헤드(head)부분부터 시작하여 원하는 원소에 도달할 때까지 next포인터를 따라 이동해야 합니다. 그러므로 i번째 원소에 접근하려면 연결 리스트 내부를 i번 이동하는 작업이 필요합니다. 원소 접근 시간은 o(n)입니다.

 

연결 리스트에 새 원소 추가하기

i=1 과 i=3의 사이에 새로운 노드 i=2를 추가하는 과정

새로운 원소를 삽입하려면 새로운 노드를 생성하고, 각 노드의 next 포인터를 수정합니다. 새로 추가한 노드(i=2)가 다음 노드(i=3)을 가리키게 만듭니다. 이전 노드(i=1)이 다음 노드(i=3)을 가리키던 것을 제거하고 새로운 노드(i=2)를 가리키게 설정합니다.