Linked List

이번에는 순차 자료구조 중 첫번째 Linked List를 학습하였다.

 

Liked List는 C언어의 순차적으로 저장되는 배열과 비슷하지만, 저장되는 메모리 주소가 직접적 연결되어 있지 않고 논리적인 포인터를 활용하여 다음 값의 주소값을 이전값이 가지고 있다는 특징이 있다.

 

 

 

이로인해 배열 중간에 값을 추가할때 시간복잡도가 훨씬 효율적이다.

 

먼저 Linked List의 ADT를 정리하였다.

 

Operations: void ListInit (List * plist); - 초기화 할 리스트이 주소값 인자로 전달 - 리스트 생성 후 제일 먼저 호출 되어야 함 void LInstert (List * plist, Ldata data); - 첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다. - 데이터의 참조를 위한 초기화가 진행된다. - 참조 성공 시 TRUE(1) 실패 시 FLASE(0) reutn int LNext(List * plist, LData * pdata); - 참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장됨 - 순차적 참조를 위해 반복 호출 가능 - 참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 함 - 참조 성공 시 TRUE(1) 실패 시 FALSE(0) 반환 LData LRmove (List * plist); - LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다. - 삭제된 데이터는 반환 - 마지막 반환 데이터를 삭제하므로 연이은 반복 호출 허용 안됨 int LCount (List * plist); - 리스트에 저장되어 있는 데이터의 수 반환

Linked List 헤더 파일