연결리스트_단일방향 연결리스트 구현

C를 통해 구현을 할 예정이다.

 

연결리스트의 특성에 맞게,

노드를 동적으로 생성하고, 그 노드들을 연결시켜주면서 연결리스트는 완성이 된다.

 

C에서는 malloc함수와 Free함수를 활용하여 메모리에 동적할당한다.

 

일단 노드를 struct를 이용하여 구성한다.

typedef struct _node
{
	int data;		// 데이터를 담을 공간 (int형)
	struct _node * next;    // 다음 노드(구조체)를 가리킬 next라는 이름의 포인터이다.
} Node;

 

이렇게 구성된 노드를 계속해서 이어주는 자료구조라고 보면 된다.

필요할때마다 Node를 하나씩 동적할당하여 이들을 연결하는 것이다.

 

동적 할당하는 코드는 아래와 같다.

newNode = (Node*)malloc(sizeof(Node));

 

역시나 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) 반환

LData LRemove(List * plist);
- LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제
- 삭제된 데이터는 반환
- 마지막 반환 데이터를 삭제하므로 연이은 반복호출을 허용하지 않는다.

int LCount(List * plist)
- 리스트에 저장되어 있는 데이터의 수를 반환

void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));
- 리스트의 정렬의 기준이 되는 함수를 등록

 

새 노드를 추가할때 두가지 방법이 있다.

(리스트의 머리에 저장하는 방법, 꼬리에 추가하는 방법)

 

머리

- 장점: 포인터 변수 tail이 불필요하다.

- 단점 : 저장된 순서를 유지하지 않는다.

 

꼬리

- 장점: 저장된 순서가 유지된다.

- 단점: 포인터 변수 tail이 필요하다.

 

윤성우의 자료구조에서는 머리에 추가하는 방법을 설명하고 있다.

"포인터 변수 tail을 유지하기 위해 넣어야 할 부가적인 코드가 번거롭고, 리스트 자료구조는 저장된 순서를 유지해야하는 자료구조가 아니다"

 

우리는 더미노드를 추가하고 tail을 제거한 연결리스트를 구현할 것이다.

 

연결리스트를 의미하는 구조체를 별도로 정의하여 활용한다.

typedef struct _linkedList
{
	Node * head;	// 더미 노드를 가리키는 멤버
	Node * cur;	// 참조 및 삭제를 돕는 멤버
	Node * before;	// 삭제를 돕는 멤버
	int numOfData;	// 저장된 데이터의 수
	int (*comp)(LData d1, LData d2);	// 정렬의 기준을 등록하기 위한 멤버
} LinkedList;

 

나머지 구현 내용은 아래 링크를 참조 바랍니다.

https://github.com/GTAEKI/DataStructure_Study/tree/main/LinkedList/DLinkedList