6-2. 연결리스트 (단순 연결 리스트)

연결리스트

- 리스트의 항목들을 노드(node)라고 하는 곳에 분산하여 저장

- 노드는 데이터 필드와 링크 필드로 구성

데이터 필드: 리스트의 원소, 즉 데이터 값을 저장하는 곳

링크 필드: 다른 노드의 주소 값을 저장하는 장소(포인터)

 

장점

- 삽입, 삭제가 용이하다. 시간 복잡도는 O(1)

- 연속된 메모리 공간이 필요 없고, 크기 제한이 없다.

단점

- 구현이 어렵고, 오류가 발생하기 쉽다.

 

연결 리스트의 종류: 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트

 

단순 연결 리스트

- 하나의 링크 필드를 이용하여 연결, 마지막 노드의 링크 값은 NULL

단순 연결 리스트의 연산

- insert_first(): 리스트의 시작 부분에 항목 삽입

- insert(): 리스트의 중간 부분에 항목 삽입

- delete_first(): 리스트의 첫 번째 항목을 삭제

- delete(): 리스트의 중간 항목을 삭제

- print_list(): 리스트를 방문하여 모든 항목 출력

 

노드의 정의

 

첫 번째 노드에 삽입

 

pre 뒤에 새로운 노드 삽입 함수

 

첫 번째 노드 삭제

 

pre가 가리키는 다음 노드 삭제 함수

 

노드 출력 함수