[자료구조] 연결 리스트

리스트

• 리스트는 자료를 정리하는 방법 중의 하나로 To_Do_List와 같은 형식을 사용한다.

 

리스트 ADT

객체: n개의 element형으로 구성된 순서 있는 모임
연산:
	insert(list, pos, item) ::= pos 위치에 요소를 추가한다.
    insert_last(list, item) ::= 맨 끝에 요소를 추가한다.
    insert_first(list, item) ::= 맨 처음에 요소를 추가한다.
    delete(list, pos) ::= pos 위치의 요소를 제거한다.
    clear(list) ::= 리스트의 모든 요소를 제거한다.
    get_entry(list, pos) ::= pos 위치의 요소를 반환한다.
    get_length(list) ::= 리스트의 길이를 구한다.
    is_empty(list) :: = 리스트가 비었는지를 검사한다.
    is_full(list) ::= 리스트가 꽉 찼는지를 검사한다.
    print_list(list) ::= 리스트의 모든 요소를 표시한다.

 

 

 

배열로 구현된 리스트

순차적인 메모리 공간을 할당하는 방식으로 순차적 표이라고도 한다.

 

 

연결 리스트

• 노드 = 데이터필드 + 링크필드
• 헤드포인터 - 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수
• 마지막 노드의 링크 필드는 NULL로 설정

 

연결 리스트의 삽입

insert_first(head, value):
1. p <- malloc()
2. p -> data <- value
3. p -> link <- head
4. head <- p
5. return head

 

insert(head, prem value):
	p <- malloc()
	p -> data <- value
	p -> link <- pre -> link
    pre -> link <- p
    return head

 

연결 리스트의 삭제

delete_first(head):
	removed <- head
    head <- head -> link
    free(removed)
    return head

 

delete(head, pre):
	removed <- pre -> link
    pre -> link <- removed -> link
    free(removed)
    return head

 

 

노드값 탐색 알고리즘

ListNode* search_list(ListNode *head, element x)
{
	ListNode *p = head;
    
    while(p != null){
    	if (p -> data == x) return p;
        p = p -> link;
    }
    return Null;
}

 

 

두 개의 리스트를 하나로 합치는 알고리즘

ListNode* concat_list(ListNode *head1, ListNode *head2)
{
	if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    else {
    	ListNode = *p;
        p = head1
        while (p -> link != NULL)
        	p = p -> link;
        p -> link = head2
        return head1;
    }
}

 

 

 

 

원형 연결 리스트

원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트이다.

즉, 마지막 노드의 링크 필드가 NULL이 아니라 첫 번째 노드 주소가 되는 리스트이다.

 

 

 

이중 연결 리스트

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

링크가 양방향이므로 양방향 검색이 가능하다.

단점 : 공간을 많이 차지하고 코드가 복잡해진다.

 

 

 

연결 리스트로 구현한 스택

#include <stdio.h>
#include <malloc.h>

typedef int element;
typedef struct StackNode {
	element data;
	struct StackNode *link;
} StackNode;

typedef struct {
	StackNode *top;
} LinkedStackType;
// 초기화 함수
void init(LinkedStackType *s)
{
	s->top = NULL;
}
// 공백 상태 검출 함수
int is_empty(LinkedStackType *s)
{
	return (s->top == NULL);
}
// 포화 상태 검출 함수
int is_full(LinkedStackType *s)
{
	return 0;
}
// 삽입 함수
void push(LinkedStackType *s, element item)
{
	StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
	temp->data = item;
	temp->link = s->top;
	s->top = temp;
}
void print_stack(LinkedStackType *s)
{
	for (StackNode *p = s->top; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}
// 삭제 함수
element pop(LinkedStackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		StackNode *temp = s->top;
		int data = temp->data;
		s->top = s->top->link;
		free(temp);
		return data;
	}
}
// 피크 함수
element peek(LinkedStackType *s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		return s->top->data;
	}
}

 

 

 

연결된 큐 삽입/삭제 연산

// 삽입 함수
void enqueue(LinkedQueueType *q, element data)
{
	QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
	temp->data = data; 		// 데이터 저장
	temp->link = NULL; 		// 링크 필드를 NULL
	if (is_empty(q)) { 		// 큐가 공백이면
		q->front = temp;
		q->rear = temp;
	}
	else { 		// 큐가 공백이 아니면
		q->rear->link = temp;  // 순서가 중요
		q->rear = 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; // front를 다음노드를 가리키도록 한다.
		if (q->front == NULL) 	// 공백 상태
			q->rear = NULL;
		free(temp); 			// 동적메모리 해제
		return data; 			// 데이터 반환
	}
}