1. 연결리스트(Linked List)

(1) 정의

• 노드 구성: 연결 리스트의 각 노드는 데이터 필드(Data Field)와 링크 필드(Link Field)로 구성된다. 데이터 필드에는 값을 저장하며, 링크 필드에는 다음 노드의 주소(포인터)가 저장된다.
• 헤드 포인터: 연결 리스트는 첫 번째 노드를 가리키는 헤드(head)포인터가 필요하다. 이를 통해 리스트의 시작점을 알 수 있다.
  
• 리스트 연결: 포인터를 통해 각 노드가 다음 노드의 위치를 가리키는 구조를 가지고 있습니다. 이를 통해 전체 노드가 논리적으로 연결된다.
• 마지막 노드: 리스트의 마지막 노드는 다음 노드를 가리킬 필요가 없으므로, 해당 노드의 링크 필드는 Null(또는 Nil)로 설정된다.
• 비연속적 메모리: 연결 리스트의 노드들은 메모리 상에서 연속적일 필요가 없다. 이는 각 노드가 자신의 다음 노드의 주소를 직접 가리키고 있기 때문이다.
• 단점: 링크 필드로 인한 기억공간이 많이 필요하며(메모리 오버헤드), 알고리즘 구현이 복잡하고, 임의의 노드를 탐색할 때는 처음 노드부터 접근하므로 비효율적이다.