자료구조 - 연결 리스트

안녕하세요 

이번 글은 자료구조 중에서 연결 리스트에 대한 글입니다.

 

연결 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다.

데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와 연결하는 역할을 하고 있습니다.

연결 리스트는 추가와 삭제가 O(1)의 시간에 가능하다는 장점이 있습니다.

하지만 데이터를 검색해 내는 데에는 O(n)의 시간이 걸리는 단점을 갖고 있습니다.

 

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있습니다.

 

단일 연결 리스트

단일 연결 리스트는 각 노드에 데이터 공간과 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다.

 

이중 연결 리스트

이중 연결 리스트는 각 노드에 데이터 공간과 두 개의 포인터 공간이 있고, 각각의 포인터는 

앞의 노드와 뒤의 노드를 가리킵니다.

 

원형 연결 리스트

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다.