[씨언어] 자료구조-링크드리스트

1. 링크드리스트 개념

링크드리스트는 데이터를 순차적으로 연결하여 저장하는 자료구조이다. 고정된 크기의 배열과 달리, 링크드리스트는 동적으로 크기를 조절할 수 있어 메모리 효율성을 높이는 특징이 있다. 각 데이터 요소는 노드(node)라고 불리며, 이 노드들은 데이터 자체와 다음 노드를 가리키는 포인터로 구성된다. 이러한 구조는 데이터 삽입과 삭제가 빠르고 유연하다는 장점을 제공한다. 구체적으로, 링크드리스트는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등으로 나뉜다. 단일 연결 리스트는 각 노드가 뒤의 노드만 가리키는 구조이고, 이중 연결 리스트는 앞뒤 노드 모두를 가리키는 포인터를 포함하여 양방향 탐색이 가능하게 된다. 원형 연결 리스트는 마지막 노드의 포인터가 처음 노드를 가리키도록 구성되어 원형 구조를 띤다. 링크드리스트의 주요 특징 중 하나는 삽입과 삭제 연산이 배열보다 효율적이라는 점이다. 예를 들어, 배열은 특정 위치에 원소를 삽입하거나 삭제할 때 전체 데이터를 이동시켜야 하는 반면, 링크드리스트는 포인터 수정만으로 빠르게 처리할 수 있다. 그러나 랜덤 접근 속도는 배열에 비해 낮아, 특정 위…