[알고리즘 9] 단순 연결 리스트

단순 연결 리스트 

단순 연결 리스트란 ?

-개념 : 한 방향으로 연결되어있고 , 마지막 노드 링크 필드값이 NULL 인 연결 리스트. 

단순 연결 리스트의 특징  

• 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진다.

• 연결 리스트에서 각 요소는 노드(Node)로 이루어 진다.

• 노드는 구조체로 구현하며, 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.

• 자주 변경되는 상황에서는 배열리스트보단 연결리스트가 비용적인 측면에서 효율적이다.
•  한 노드에서 역방향으로 노드를 탐색 할 수 없으며 이를 진행 하려면 별도의 포인터가 필요하다는 단점이 있다.

단순 연결 리스트 정의

단순 연결 리스트의 노드 탐색 알고리즘

• 리스트의 노드를 처음 부터 하나씩 순회하면서 현재 노드의 데이터 필드값과 x값과 비교하여 찾는다.

• 포인터 linked_list_h에 리스트 A의 시작주소를 저장하고 linked_list_h가 NULL이 아닌 동안 탐색 연산 반복한다.
  

  → linked_list_h노드의 데이터 필드 값이 탐색 값 x와 같으면 linked_list_h값 retur은 탐색 성공으로 현재 필드 값과 탐색 값 x와 같지 않으면 탐색을 계속해야 하므로 링크를 따라 다음 노드로 이동한다.

• linked_list_h값 NULL값 반환은 탐색값 x가 리스트 A에 없다는 의미로 탐색 실패다.