07 연결리스트2 (C언어로 쉽게 풀어쓴 자료구조)

7.1 원형 연결 리스트

원형 연결리스트의 소개

반가웡

원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 리스트(원래는 NULL이었는데!)

 

장점: 하나의 노드에서 다른 모든 노드로의 접근이 가능하다(링크만 따라서 쭉쭉 가면 되니까!) = 삽입/삭제가 단순연결리스트보다 용이하다

특히 insert_last가 매우 효율적이다. 단순연결리스트에서는 첫 번째 노드부터 쭉쭉 링크 따라서 가야지만 마지막 노드에 도달할 수 있었는데 원형 연결 리스트에서는 head포인터가 마지막을 가리키도록 해주기만 하면 된다.

 

원형 연결리스트의 정의

원칙적으로 헤드포인트만 있으면 된다

ListNode *head;

 

insert_first()

헤드포인터 head가 마지막 노트를 가리키고 있다는 것에 유의해야한다

 

insert_last()

위 코드에 head=node만 추가해주면 마지막 노드를 가리키는 head가 추가된 node를 가리키게 되어 걔가 마지막 위치에 추가된 게 된다!

 

7.2 원형 연결 리스트는 어디에 사용될까?

1.컴퓨터에서 여러 응용 프로그램을 하나의 CPU를 이용하여 실행할 때: 운영체제는 모든 응용프로그램이 완료될 때까지 연결 리스트를 계속 순회한다

2.멀티 플레이어 게임

3.원형 큐를 만드는데 사용

 

7.3 이중 연결 리스트

단순연결리스트에서는 후행노드를 찾기는 쉽지만 선행노드를 찾기는 어렵다. 얘를 해결하는 게 바로 이중연결리스트!

이중연결리스트: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트

 

장점: 양방향 검색이 가능
단점: 공간 많이 차지 & 코드 복잡

 

이중연결리스트+원형연결리스트

여기서는 헤드 포인터가 아닌 헤드 노드가 쓰였다는 걸 주의하자! 헤드 노드는 데이터 필드에 아무런 정보도 없다. 얘는 삽입, 삭제 알고리즘이 매우 편해지기 때문에 사용한다.

 

링크필드는 포인터로 이루어진다

 임의의 노드를 가리키는 포인터를 p라고 해보자

p = p->llink->rlink = p->rlink->llink

앞뒤로 똑같이 이동할 수 있음을 나타낸다

llink는 선행노드를, rlink는 후행노드를 가리킨다

 

dinsert()

 

ddelete()

7.4 예제: mp3 재생 프로그램 만들기

7.5 연결리스트로 구현한 스택

연결된 스택(linked stack)

배열로 구현한 스택과 달리 크기가 제한되지 않는다는 엄청난 장점!

동적 메모리 할당만 하면 새로운 요소 삽입이 가능하지만, 동적 메모리 할당/해제 과정에서 삽입/삭제 시간이 늘어난다는 게 단점이 되기도 한다

 

삽입(push)=insert_first

삭제(pop)=

 

 

7.6 연결 리스트로 구현한 큐

연결된 큐

연결리스트로는 큐도 만든다.. 이제 슬슬 좀 짜증나는 것 같기도..?(그만해!!! 멈춰!!!)

큐는 앞에서 삭제 뒤에서 삽입하니까 front는 삭제와 관련된 포인터이고 rear은 삽입과 관련된 포인터이다

큐가 공백일 경우 front=rear=NULL이 된다.

 

삽입연산

연결리스트로 구현된 큐에서는 삽입연산을 큐가 공백일 때와 아닐 때로 구분해서 생각한다

 

<큐가 공백일 때>

front와 rear가 그냥 삽입할 새로운 노드를 가리키게 하면 된다

 

<큐가 공백이 아닐 때>

큐가 공백이 아닐 때는 rear가 가리키고 있는 노드와 새로운 노드를 연결하고, rear가 새로운 노드를 가리키도록 변경해줘야 한다.

 

void enqueue(LinkedQueueType *q, element data)
{
    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    temp->data=data;
    temp->link=NULL;
    //큐가 공백일 때
    if(is_empty(q)) {
        q->front = temp;
        q->rear = temp;
    }
    //큐가 공백이 아닐 때
    else {
        q->rear->link = temp;
        q->rear = temp;
    }
}

 

삭제연산

삭제할 애(젤앞)을 temp로 만들어버릴 거다

element dequeue(LinkedQueueType *q)
{
    QueueNode *temp = q->front;
    element data;
    if(is_empty(q)) {
        fprintf(stderr, "큐가 비어있음\n");
        exit(1);
    }
    else {
        data = temp->data;
        q->front = q->front->link
        if(q->front == NULL)
            q->rear == NULL;
        free(temp);
        return data;
    }
}