#28 [C 자료구조] 원형 연결 리스트/이중 연결 리스트

리스트도 큐와 마찬가지로 원형 연결 리스트가 있다! 워후!

또한 앞 뒤로 연결이 가능한 이중 연결 리스트도 있다! 워후!

다재다능한 두 리스트의 활용법을 오늘 알아보도록 하자.

한 번에 많은 포스팅을 올리니 체력 고갈이 심하다.

 

 

원형 연결 리스트(Circular Linked List)

 

마지막 노드가 리스트의 첫 노드를 가리키는 형태의 리스트다.

마지막 노드에 대한 포인터 last가 그대로 있다. 이는 새로운 노드 삽입용!!

 

원형 연결 리스트 생성 코드를 봐보자

 

1) 노드 생성 스트럭쳐 구성

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

기계와 같이 연결리스트를 만들어 준다.

이제 프로라면 가능해야한다. 일단 난 아님

 

2) 노드 삽입 함수

void insertFront (NODE *last, NODE *node){
	if (!last) { //빈 연결 리스트라면
    	last = node;
        node -> link = node; //자기 참조 노드
    }
    else {
    	node -> link = (last) -> link; //첫 노드를 새 노드에 연결 시킴
        (last) -> link = node; // last에 해당하는 node가 자신을 참조하게 만듦
    }
}

 

3) last까지의 길이 계산하기

int length(NODE *last){
	NODE *temp; // 일시적으로 temp 만듦
    int count = 0;
    if (last) {
    	temp = last; 
        do {
        	count++;
            temp = temp -> link; //temp 를 계속 다음 노드를 가리키게 만듦. 다시 돌아올 때 까지
        } while (temp != last);
    }
    return count;
}

---

 

 

 

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트는 단순 연결 리스트의 앞의 노드가 무엇인지 모른다는 단점을 극복하기 위해 만들어졌다. 따라서 각 노드에 값뿐만 아니라 양방향 링크를 넣는다(llink, rlink). 

뭐, 단점은 메모리 공간을 하나 더 사용한다는 점과 복잡한 코딩이 기다린다는 점이다.

 

1) 이중 연결 리스트 스트럭쳐 구성하기

typedef struct {
	int key;
} element;

typedef struct node nodePointer;
typedef struct node {
    nodePointer *llink;
    element item;
    nodePointer *rlink;
};

두 개의 노드 사이에 있는 하나의 노드를 만들었다.

 

2) 노드 사이 삽입하는 함수 만들기

void dinsert(nodePpointer *node, nodePointer *newnode) {
    newnode -> llink = node;
    newnode -> rlink = node -> rlink;
    node -> rlink -> llink = newnode;
    node -> rlink = newnode;

이는 직관적으로 이해하기 힘드니 그림과 함께 순서를 파악해야한다.

3) 노드 삭제하는 함수 만들기

void ddelete(nodePointer *node, nodePointer *deleted) {
	if (node == deleted)
    	printf("Head 삭제 불가\n");
    else {
    	deleted -> link -> rlink = deleted -> rlink;
        deleted -> rlink -> llink deleted -> llink; //위와 순서 상관 무
        free(deleted);
    }
}

쉽다.

 

 

헤드 노드

이중 연결 리스트에는 헤드 노드를 사용하면 좀 더 연산을 쉽게 수행한다.

item에 값이 없는 이 헤드 노드는 공백 리스트로 단순히 연결 구조를 한번 꼬아줌으로써 연산에 편의성을 더해준다.

---

 

 

이제 리스트의 개념에 대해서 대부분 다 알아보았다. 다음 시간엔 드.디.어

즐거운 연결 리스트의 응용과 실전에 들어간다. ^3^