알고리즘/자료구조

선형 자료구조 - 2. 연결 리스트

연결 리스트 (Linked List)

연결 리스트는 데이터를 링크로 연결해서 관리하는 자료구조입니다.

연결 리스트는 노드(Node)라는 저장 단위로 구성되며, 노드는 값과 포인터를 가지고 있습니다.

값은 저장하려는 값, 포인터는 다음/이전 노드의 연결 정보를 뜻합니다.

자료의 순서는 정해져있지만, 배열과는 다르게 메모리에 연속적으로 저장되지는 않습니다.

배열과는 다르게 데이터 공간을 미리 할당할 필요가 없어서 데이터의 추가와 삭제가 용이합니다.

배열 같은 경우, 사용하지 않는 만큼 공간 낭비가 생기는데, 그러한 공간낭비가 줄어듭니다.

데이터 뿐만 아니라 다음 데이터의 위치정보까지 같이 저장하다보니 링크를 위한 별도 데이터 공간이 필요합니다.

더불어, 다음 데이터와의 연결정보를 통해 접근하다보니 배열에 비해 상대적으로 접근 속도가 느립니다.

데이터의 추가/삭제 시, 링크를 재연결해주는 작업을 해야합니다.

💡 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리

한 노드가 다음 노드에 대한 참조만을 가지는 가장 단순한 형태의 연결 리스트 입니다.

HEAD를 잃어버리면 전체를 못쓰게 되므로 안정적인 구조는 아닙니다.

다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키는 것이 이중 연결 리스트입니다.

마지막 노드의 다음 참조를 처음 노드를 가리키도록 한 것이 순환 연결 리스트입니다.

자바에서는 LinkedList라는 자료형을 제공해주고 있습니다.

참고자료

Contents