[C language] linked list , circular , invert , 연결 리스트 , 원형 연결 리스트 역순 출력

연결 표현 방법 ( linked representation )과 연결 리스트 ( linked list )

순차 (sequential) 표현의 문제점은 연결 표현으로 해결할 수 있다.

순차표현 : 연속된 리스트의 원소들이 일정한 거리만큼 떨어져 저장. 원소들의 저장 순서가 리스트에 표현된 순서와 동일

연결 표현 : 각 원소들이 메모리 내 어떤 곳에나 위치 가능. 원소들의 저장 순서가 리스트에 표현된 순서와 반드시 똑같을 필요가 없다.

연결 표현 방법에서는 각 리스트의 원소들에 대하여 다음 원소를 가리키는 포인터(pointer) 또는 링크(link)가 연관되어 있다.

일반적으로 연결 리스트는 노드들을 포함하는데, 이 노드들은 데이터 필드와 링크 필드로 이루어져 있다.

주로 이런 구조로 이루어진다.

link 는 다음  원소를 가리키고, 마지막 link는 NULL을 가리킨다.

 

연결 리스트 노드 ( linked list node )

자기 참조 구조를 가진다.

구조체 struct 로 만들었다.

typedef struct listnode *nodePtr;
typedef struct listnode {
 		int data;		//data field
                nodePtr link;	//link field
};

 

연결 리스트 만들기 ( create linked list )

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

typedef struct listnode *nodePtr;
typedef struct listnode {
    int data;
    nodePtr link;
};

nodePtr createTwoNodes(){       //2개의 노드를 생성하고, 첫번째 노드를 리턴.
    nodePtr first, second;
    first = (nodePtr)malloc(sizeof(*first));
    second = (nodePtr)malloc(sizeof(*second));
    first->data = 10;
    first->link = second;
    second->data = 20;
    second->link = NULL;

    return first;
}

void printLinkedList(nodePtr node){
    printf("List : ");
    for (; node; node = node->link)
        printf("%4d ", node->data);
    printf("\n");
}

int main(){
    nodePtr first = createTwoNodes();
    printLinkedList(first);

    return 0;
}

 

연결 리스트 삽입 ( linked list insert )

void insert(nodePtr *first, nodePtr x){
    nodePtr temp;
    temp = (nodePtr)malloc(sizeof(*temp));
    temp->data = 30;
    if (*first){                            //리스트가 공백이 아닌 경우
        temp->link = x->link;
        x->link = temp;
    }else{                                  //리스트가 공백인 경우
        temp->link = NULL;
        *first = temp;
    }
}

void printLinkedList(nodePtr node){
    printf("List : ");
    for (; node; node = node->link)
        printf("%4d ", node->data);
    printf("\n");
}

int main(){
    nodePtr first = createTwoNodes();
    printLinkedList(first);
    insert(&header, first);
    printLinkedList(first);

    return 0;
}

 

 

연결 리스트 삭제 ( linked list delete )

trail은 삭제될 x의 선행 노드이고, first는 리스트의 시작이다.

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

 

원형 연결 리스트 역순 출력 ( linked list invert )

2개의 노드를 가진 원형 리스트의 역순을 출력한다. circular list invert

원형 리스트 이기 때문에 프린트는 3번만 하였다.

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

typedef struct node *linkPointer;
typedef struct node {
	int data;
	struct node *link;
}Node;

linkPointer reverse(linkPointer lead)
{
	if (lead->link == lead || lead == NULL) 
		return lead;

	linkPointer prev, cur, next, last;

	last = lead;
	prev = lead;
	cur = lead->link;
	lead = lead->link;
	while (lead != last) {
		lead = lead->link;
		cur->link = prev;
		prev = cur;
		cur = lead;
	}
	cur->link = prev;
	lead = prev;
    reutrn lead;
}

int main(){
	/********           L2             ********/
	linkPointer *L2;
	Node* Node1 = (Node*)malloc(sizeof(Node));
	L2 = Node1;
	Node1->data = 10;
	Node* Node2 = (Node*)malloc(sizeof(Node));
	Node1->link = Node2;
	Node2->data = 20;
	Node2->link = Node1;
	/********           print L2              *******/
	Node *curr = L2;
	int i = 0;
	while (i < 3) {					
		printf("주소: %d, 데이터: %d, 링크: %d\n", curr, curr->data, curr->link);
		curr = curr->link;
		i++;
	}
	printf("\n");
	/********           invert 후 print L2              *******/
	curr = reverse(L2);
	i = 0;
	while (i<3) {
		printf("주소: %d, 데이터: %d, 링크: %d\n", curr, curr->data, curr->link);
		curr = curr->link;
		i++;
	}
	free(Node1);
	free(Node2);
	return 0;
}

과제로 했던 코드이다.

 

 

(Fundamentals of Data Structures in C - Horowitz . Sahni Anderson-Freed 참고.)