[C언어 자료구조] 3.1 연결리스트 설계

[C언어 자료구조] 3.1 연결리스트 설계

---

 동적 배열처럼 연결리스트도 동적으로 생성한 개체는 형식에 관계없이 보관할 수 있게 정의할게요. 사용하기 편리하게 void * 형식을 Element 형식으로 타입 재지정할게요.

typedef void * Element;

 

 연결리스트는 노드의 선형 집합입니다. 노드는 링크와 데이터의 조합으로 여기에서는 두 개의 링크를 갖는 노드를 정의할 것입니다.

typedef struct _Node Node;

typedef Node *Link;

struct _Node

{

    Link next;

    Link prev;

    Element data;

};

 

 연결리스트 구조체에는 맨 앞에 있는 더미 노드의 위치 정보인 head와 맨 뒤에 있는 더미 노드의 위치 정보인 tail과 보관한 자료 개수를 멤버로 구성할게요.

typedef struct _LinkedList LinkedList;

struct _LinkedList

{

    Link head;

    Link tail;

    int usage;

};

 

 연결리스트를 동적으로 생성하는 함수와 소멸하는 함수를 선언합시다.

LinkedList *New_LinkedList();

void Delete_LinkedList(LinkedList *linkedlist);

 

 연결리스트에 순차적으로 보관하기 위한 함수를 제공합시다.

void LinkedList_PushBack(LinkedList *linkedlist,Element data);

 

 원하는 노드 앞에 보관하는 함수도 제공합시다. 여기에서는 노드의 위치 정보를 Link로 타입 재지정한 것을 기억하세요.

void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data);

 

 맨 앞에 보관한 자료가 있는 노드의 위치 정보를 구하는 함수와 맨 뒤에 보관한 자료가 있는 노드의 다음 노드 위치를 구하는 함수를 제공합시다.

Link LinkedList_Begin(LinkedList *linkedlist);

Link LinkedList_End(LinkedList *linkedlist);

 

 특정 위치의 노드를 제거하는 함수도 제공합시다.

void LinkedList_Erase(LinkedList *linkedlist,Link pos);

 

 연결리스트는 배열과 다르게 자료를 저장하는 저장소가 연속적인 메모리에 할당하는 것이 아니라 독립적인 노드에 보관하고 단지 노드의 링크가 다른 노드의 위치를 알고 있는 것입니다. 따라서 인덱스 연산으로 보관한 자료를 변경하거나 얻어오는 기능은 제공하지 않을게요.

 

 또한 인덱스로 배열을 사용하기 전에 디폴트 값으로 최대 보관할 자료 개수만큼 설정하는 함수도 제공하는것이 별다른 의미가 없어 제공하지 않기로 합시다.

 

//LinkedList.h

#pragma once

typedef void * Element;

typedef struct _Node Node;

typedef Node *Link;

struct _Node

{

    Link next;

    Link prev;

    Element data;

};

 

typedef struct _LinkedList LinkedList;

struct _LinkedList

{

    Link head;

    Link tail;

    int usage;

};

 

LinkedList *New_LinkedList();

void Delete_LinkedList(LinkedList *linkedlist);

void LinkedList_PushBack(LinkedList *linkedlist,Element data);

void LinkedList_Insert(LinkedList *linkedlist,Link pos,Element data);

Link LinkedList_Begin(LinkedList *linkedlist);

Link LinkedList_End(LinkedList *linkedlist);

void LinkedList_Erase(LinkedList *linkedlist,Link pos);