[자료구조] 연결리스트 (1) 단순연결리스트

📕리스트: 항목들이 차례대로 저장되어 있는 것

리스트의 항목들은 순서 또는 위치를 가진다. 스택과 큐도 넓게 보면 리스트의 일종이다. 리스트는 스택, 큐와 마찬가지로 삽입 삭제 연산이 가능할 뿐만 아니라 특정한 항목을 찾는 탐색 연산도 가능하다.

(1)배열을 이용한 리스트의 구현
=> 간단하지만, 크기가 고정되어 있는 단점이 있다.

#include <stdio.h>
#include <stdlib.h>
#define N 100

typedef int element;
typedef struct ListType
{
    element data[N];
    int size;
}ListType;

void init(ListType* L)
{
    L->size = 0;
}

int isFull(ListType* L)
{
    return L->size == N ; //배열이 99까지 찼다면, 크기는 100이 될 거니까
}

int isEmpty(ListType* L)
{
    return L->size == 0;
}

void insertLast(ListType* L, element e)
{
    if(isFull(L))
    {
        printf("Overflow!\n");
        return;
    }
    else
        L->data[L->size++] = e;
}

void insertFirst(ListType* L, element e)
{
    if(isFull(L))
    {
        printf("Overflow!\n");
        return;
    }
    else
    {
        for(int i=L->size-1;i>=0;i--)
            L->data[i+1] = L->data[i];
        L->data[0] = e;
    }
    L->size++;
}

void insert(ListType* L, int pos, element e)
{
    if (isFull(L))
	{
	    printf("FULL!\n");
	    return;
	}
    if(pos < 0 || pos > L->size)
    {
         printf("포지션 입력 오류! \n");
         return;
    }
    for(int i=(L->size-1);i>=pos ;i--)
    {
        L->data[i+1] = L->data[i];
    }
    L->data[pos] = e;
    L->size++;
}

void clear(ListType* L)
{
    L->size = 0;
}

element delete(ListType* L, int pos)
{
    if(isEmpty(L))
    {
        printf("Underflow!\n");
    }
    if(pos < 0 || pos > L->size)
        printf("포지션 입력 오류!\n");
    element e = L->data[pos];
    for(int i=pos;i<(L->size-1);i++) //이동해야 할 값이 3개면 이동 연산은 2번 이루어짐
    {
        L->data[i]=L->data[i+1];
    }
    L->size--;
    return e;
    
}

element deleteLast(ListType* L)
{
    if(isEmpty(L))
    {
        printf("Underflow!\n");
    }
    
    int i = L->size -1;
    L->size--;
    return L->data[i];
    
}

element getPosition(ListType* L)
{
    int key;
    printf("위치를 찾고싶은 값을 입력하세요: ");
    scanf("%d", &key);
    for(int i=0 ; i<L->size ; i++)
    {
        if(key == L->data[i])
            return i;
    }
    return -1;
}
element getEntry(ListType* L, int pos)
{
    if(isEmpty(L))
    {
        printf("Underflow!\n");
    }
    if(pos < 0 || pos > L->size)
        printf("포지션 입력 오류!\n");
    return L->data[pos];
}

element getLength(ListType* L)
{
    if(isEmpty(L))
    {
        printf("Underflow!\n");
    }
  
    return L->size;
}

void print(ListType* L)
{
    if(isEmpty(L))
    {
        printf("출력할 내용이 없습니다.\n");
        return;
    }
    for(int i=0;i<(L->size);i++)
    {
        printf("[%d] -> ", L->data[i]);
    }
    printf("\b\b\b  \n");
}
int main()
{
    ListType L;
	init(&L); //리스트 전달

	insertLast(&L, 10); print(&L);
	insertLast(&L, 20); print(&L);
	insertLast(&L, 30); print(&L);
	 

	insert(&L, 1, 40); print(&L);
	insert(&L, 2, 50); print(&L);
	insert(&L, 3, 60); print(&L);

	printf("[%d] is deleted.\n", deleteLast(&L)); print(&L);
    int idx=getPosition(&L);
    if(idx == -1)
        printf("찾으시는 값이 없습니다.\n");
    else
        printf("[%d]의 위치에 있습니다.\n", idx);
    

    return 0;
}

💡 리스트는 포지션을 기준으로 이동시킬건지, 사이즈를 기준으로 이동시킬건지 생각하면 간단하다.

(2) 연결리스트

<#include <stdio.h>
#include <stdlib.h>

typedef char element;
typedef struct ListNode
{
    element data;
    struct ListNode* next; //나하고 똑같은 타입의 구조체를 가리키는 주소소
}ListNode;

typedef struct ListType
{
    ListNode* head; //노드를 가리키는 헤드포인터터
    int size; //선택적, 노드의 개수수
}ListType;

void init(ListType* L)
{
    L->head = NULL; //비어있는 리스트는 head가 아무것도 안가리킴킴
    L->size = 0;
}

int isEmpty(ListType* L)
{
    return L->head == NULL;
}

void insertFirst(ListType* L, element e)
{
    ListNode* node=(ListNode *)malloc(sizeof(ListNode));
    node->data = e;
    node->next = L->head;
    L->head = node;
    L->size++;
}

void insertLast(ListType* L, element e)
{
    ListNode* node=(ListNode *)malloc(sizeof(ListNode));
    node->data = e;
    node->next = NULL; //노드의 끝은 NULL이기 때문에
    
    if(isEmpty(L))
        L->head = node;
    else
    {
        ListNode *p = L->head;
        while(p->next != NULL)
            p=p->next;
        
        p->next = node;
    }
    L->size++;
}

void insert(ListType* L, int pos, element e)
{
    if(pos == 1)
        insertFirst(L, e);
    else
    {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        ListNode* p = L->head;
        for(int i=1;i<pos-1;i++)
            p = p->next;
        node->data = e;
        node->next = p->next;
        p->next = node;
        L->size++;
        
    }
}

element deleteLast(ListType* L)
{
    ListNode* p = L->head;
    for(int i=1;i<L->size-1;i++)
        p=p->next;
    element e = p->next->data;
    p->next=NULL;
    L->size--;
    return e;
}

element deleteFirst(ListType* L)
{
    ListNode* p = L->head;
    element e = p->data;
    L->head = p->next;
    free(p);
    L->size--;
    
    return e;
}

element delete(ListType* L, int pos)
{
    element e;
    if(pos == 1);
        e =deleteFirst(L);
    if(pos == L->size-1)
        e = deleteLast(L);
    ListNode* p = L->head; //시작, 헤드포인터터
    ListNode* q = NULL; //화살표를 두개 써서 삭제될 것과 삭제되기 전꺼 두개 가가리키
    for(int i=1;i<pos-1;i++)
    {
        q = p; //pos가 3이라면 q는 2를 가리키고
        p = p->next; // p는 삭제될 것, 3을 가리킴
    }
    e = p->data;
    q -> next = p->next;
    free(p);
    L->size--;
    return e;
}

void print(ListType* L)
{
    ListNode* p = L->head;
    for(p;p!=NULL;p=p->next)
        printf("%c => ", p->data);
    printf("\b\b\b  \n");
}
int main()
{
   ListType L;
	init(&L);

	insertLast(&L, 'E'); print(&L);
	insertFirst(&L, 'A'); print(&L);
	insertFirst(&L, 'B'); print(&L);
	
	insertLast(&L, 'C'); print(&L);
	insertLast(&L, 'D'); print(&L);

	insert(&L, 1, 'F'); print(&L);
	insert(&L, 3, 'G'); print(&L);
	insert(&L, L.size + 1, 'H'); print(&L);

	printf("[%c] is deleted,\n", deleteLast(&L)); print(&L);
	printf("[%c] is deleted,\n", deleteFirst(&L)); print(&L);
	printf("[%c] is deleted,\n", delete(&L, 3)); print(&L);
	return 0;
}