4. 연결 리스트

연결리스트 (Linked list)

노드를 연결시킨 자료구조

노드는 데이터와 포인터를 가지고 있다.

 

장점

• 길이가 가변적

단점

• 데이터를 바로 찾아낼 수 없고, 전부 탐색해야 한다.

 

노드 구조

typedef struct listNode listNode *listpoint;
typedef struct listNode{
	int data;
	listpoint link;
};

• 저렇게 정의를 어떻게 하는지 이해가 안 됐는데 암묵적 허용(?)이라고 한다.

 

두 개의 노드 가진 연결리스트 생성

listpointer create2()
{
    listpoint first, second;
    Malloc(first, sizeof(listNode);
    Malloc(second, sizeof(listNode);
    second -> link = Null;
    second -> data = 20;
    first -> data = 10;
    first -> link = second;
    return first;
}

 

노드 삽입

void insert(listpoint *firstp, listpoint x)
{
    listpoint temp;
    Mollac(temp, sizeof(*temp));
    temp -> data = 50;
    if(*first)
    {
    	temp -> link = x -> link;
        x -> link = temp;
    }
    else
    {
    	temp -> link = Null;
        *firstp = temp;
    }
}

 

노드 삭제

void delete(listpoint *firstp, listpoint trail, listpoint x)
{
    if(trail) trail -> link = x -> link;
    else *firstp = (*firstp) -> link;
    free(x);
}

1. 삭제하려는 노드가 리스트의 첫 번째 노드일 경우
   • delete(&first, NULL, first);
2. 첫 번째가 아닌 경우
   • delete(&first, y, y -> link);

 

연결리스트 역순

listpoint invert(listpoint lead)
{
    listpoint middle = NULL, trail;
    while(lead)
    {
    	trail = middle;
        middle = lead;
        lead = lead -> link;
        middle -> link = trail;
    }
    return middle;
}

 

두 개의 연결리스트 연결

listpoint concatenate(listpoint ptr1, listpoint ptr2)
{
    listpoint temp;
    if(!ptr1) return ptr2;
    if(!ptr2) return ptr1;
    for(temp = ptr1; temp -> link; temp = temp -> link);
    temp -> link = ptr2;
}

 

마지막 노드가 last인 원형리스트 앞에 노드 삽입

void insertFront(listpoint *lastp, listpoint node)
{
    if(!(*lastp)) // 연결리스트가 공백인 경우
    {
    	*lastp = node;
        node -> link = node;
    }
    else // 연결리스트가 공백이 아닌 경우
    {
    	node -> link = (*lastp) -> link;
        (*lastp) -> link = node;
    }
}

 

원형리스트 길이 계산

int length(listpoint last)
{
    listpoint temp;
    int cnt = 0;
    if(last)
    {
    	temp = last;
        do{
        	cnt++;
            temp = temp -> link;
        }while(temp != last);
    }
    return cnt;
}