c언어에서 리스트란?

리스트의 이해

 

순차 리스트

- 배열을 기반으로 구현된 리스트

 

연결 리스트

- 메모리의 동적 할당을 기반으로 구현된 리스트

 

이는 구현 방법을 기준으로 한 구분이다. 따라서 이 두 리스트의  ADT 가 동일하다고 해서 문제가 되지않는다.

 

 

리스트의 특징

- 저장형태 : 데이터를 나란히(하나의 열로) 저장한다.

- 저장특성 : 중복이 되는 데이터를 저장을 허용한다.

 

이것이 리스트의 ADT를 정의하는데  있어서 고려해야 할 유일한 내용이다.

 

 

ADT 

 

void ListInit(List* Plist);

 

- 초기화할 리스트의 주소 값을 인자로 전달한다.

- 리스트 생성 후 제일 먼저 호출되어야 하는 함수

 

void LInsert(List* Plist, LData data);

 

- 리스트에 데이터를 저장한다. 매개변수 data 에 전달된 값을 저장한다.

 

int LFirst(List* plist, LData* pdata)

 

- 첫번째 데이터가 pdata가 가리키는 메모리에 저장된다.

- 데이터의 참조를 위한 초기화가 진행된다.

- 참조 성공 시 TRUE(1), 실패시 FALSE(0) 반환

 

 

int LNext(List* plist, LData* pdata)

 

-참조된 데이터의 다음 데이터가  pdata 가 가리키는 메모리에 저장된다.

-순차적인 참조를 위해서 반복 호출이 가능하다.

-참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다.

- 참조 성공 시 TRUE(1), 실패시 FALSE(0) 반환

 

 

 

LDta LRemove(List* plist)

 

-LFirst  또는 LNext 함수의 마지막 반환 데이터를 삭제한다.

-삭제된 데이터는 반환된다.

-마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다.

 

 

int Lcount(List* plist)

-리스트에 저장되어 있는 데이터의 수를 반환한다.

 

 

LData는 저장 대상의 자료형을 결정할 수 있도록 typedef로 선언된 자료형의 이름이다.

 

 

 LNext 와  LFirst 로 나뉜이유는 조회를 위해서 LFirst 가 필요한거다. 

 

 

배열의 특징

 

- 순차접근

 

 

Node는 데이타를 담을수 있어야하고, 연결이 가능해야한다.

 

ex)

 

typedef struct _node

{

int data; // 데이터를 담을공간

struct _none* next; //연결의 도구

}Node;

 

 

연결리스트의 삼형제

 

- Node* head = 무조건 필요하고 , 첫번째 자료구조를 표시한다.

 

- Node* tail = head는 필수지만 tail을 없어도 될때도 있다.

 

- Node* cur = 순차접근