[자료구조] 연결리스트

단순 연결리스트

시간 복잡도

O(n) 또는 O(1)

 

장점: 자투리 메모리 공간 사용 

단점: 포인터 변수가 메모리를 차지함

 

배열에서 삽입연산을 하려면 다 뒤로 옮겨줘야함

삭제연산을 하려면 다 앞으로 옮겨줘야함 

---

tail 포인터는 꼭 필요한 건 아님

C

typedef struct Node{
	int data;
	Node* next;
}Node;

노드 구조체 선언

int main(){
	Node* head = NULL;
	Node* tail = NULL;
    
    for(int i = 0; i<5; i++){ //5칸짜리 연결리스트 만들기
    	Node* new_node = (Node*)mallloc(sizeof(Node)); //새 노드를 생성하고 메모리 할당
        
        new_node->data = i; //데이터 할당
        new_node->next = NULL; //새로 만들어진 노드가 맨 뒤이기 때문에 next가 NULL
        
        if(head == NULL){ //지금 노드가 첫 노드면 헤드가 된다
        	head = new_node;
        }
        else{ //아니라면 tail 뒤에 붙이기
        	tail->next = new_node;
        }
        tail = new_node; //새로 만든 노드를 tail로
    }
}

연결리스트 만들기

기능구현

포인터로 넘기면 head 반환 해서 덮어써야하고, 더블 포인터로 넘기면 값 자체를 바꿔줌 

삽입

void addFirst(int data, Node** head, Node** tail){ 
    Node* new_node = (Node*)malloc(sizeof(Node)); //메모리 할당
    
    new_node->data = data; 
    
    //순서주의 
    new_node->next = head; //맨 앞이니까 head를 가리키기
    *head = new_node; //헤드를 새 노드도 바꾸기
    
    if(tail == NULL){ //이게 처음 만들어진 노드인 경우
    	*tail = new_node; //tail도 그걸 가리켜야함
    }
}

맨 앞에 삽입

void addNode(int data, Node* pre, Node** tail){ 
    Node* new_node = (Node*)malloc(sizeof(Node)); //메모리 할당
    
    new_node->data = data; 
    
    //순서주의
    new_node->next = pre->next; //pre가 가리키던 애를 이제 새로 만든 노드가 가리키기
    pre->next = new_node; //pre가 새 노드를 가리키기
    
}

 

pre뒤에 삽입

삭제

void deleteFirst(Node** head, Node** tail){
    //순서주의
    Node* tmp = *head; //메모리 비워야 하니 지우기 전 tmp에 저장해두기    
    *head = (*head)->next; //head 변경, 사실 이게 삭제임
    free(tmp); 
    
    if(*head == NULL){ //마지막 남아있던 노드를 지운 경우
    	*tail = NULL; //tail도 비워야함
    }     
}

맨 앞을 삭제

void deleteNode(Node* pre, Node** tail){ 
    //순서주의
    Node* target = pre->next; //메모리 비워야 하니 지우기 전 삭제할 노드 저장    
    pre->next = target->next; //pre가 삭제할 노드 다음 노드 가리키기, 사실 이게 삭제임
    
    if(target == *tail){ //tail을 지운 경우
    	*tail = pre; //pre가 새로운 tail
    }
    
    free(target); //메모리 비우기
}

pre뒤를 삭제

순회

Node* cur = head; //head부터 순회 시작
while(cur != NULL){
	printf("data: %d\n", cur->data); //데이터 출력
	cur = cur->next; //다음칸으로 옮겨가기
}

리스트 순회하며 출력하기

---

역순리스트 만들기

Node* reverse(Node* head){
    Node *p, *q, *r;
    
    p = head; //현 리스트 
    q = NULL; //역순이 될 노드
    
    while(p != NULL){
        //순서주의
        r = q; //이미 역순이 된 리스트        
        q = p;
        p = p->next;
        q->next = r;
    }
    return q;
}

---

다항식

typedef struct Node{
    int coef;
    int expon;
    Node *next;
}Node;

typedef struct HeadNode{
    int size;
    Node* head;
    Node* tail;
}HeadNode;

HeadNode* create(){
    HeadNode* plist = (HeadNode*)malloc(sizeof(HeadNode*));
    
    plist->size = 0;
    plist->head = NULL;
    plist->tail = NULL;
    
    return plist
}

void poly_add(HeadNode *plist1, HeadNode *plist2, HeadNode *plist3){
    Node* a = plist1->head;
    Node* b = plist2->head;
    int sum;
    
    while(a && b){
        if(a->expon == b->expon){ //a차수 == b차수
            sum = a->coef + b->coef;
            if(sum != 0) insert_last(plist3, sum, a->expon);
            a = a->next;    
            b = b->next;    
        }
        else if(a->expon > b->expon){ //a차수 > b차수
            insert_last(plist3, a->coef, a->expon);
            a = a->next;    
        }
        else{ //a차수 < b차수
            insert_last(plist3, b->coef, b->expon);
            b = b->next; 
        }
    }
    
    //둘 중에 하나 먼저 끝나면 남은 거는 그대로 카피
    for(a != NULL; a = a->next)
        insert_last(plist3, a->coef, a->expon);
    for(b != NULL; b = b->next)
        insert_last(plist3, b->coef, b->expon);
}

---

스택

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

typedef struct{
    StackNode* top;
}LinkedStackType;

//insert_first
void push(LinkedStackType* s, element data){
    StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
    temp->data = data;
    
    temp->link = s->top;
    s->top = temp;
}

//delete_first
element pop(LinkedStackType *s){
    if(is_empty(s)) error("스택이 비어있음");
    else{
        //사라지지 않게 저장
        StackNode* temp = s->top;
        int data = temp->data;
        
        s->top = s->top->link;
        free(temp);
        return data;
    }    
}

---

큐

포인터가 두 개인 단순 연결 리스트

typedef struct QueueNode{
    element data;
    QueueNode* link;
}QueueNode;

typedef struct{    
    QueueNode* front;
    QueueNode* rear;
}LinkedQueueType;

//insert_last
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;
    }
}

//delete_first
element dequeue(LinkedQueueType *q){
    //사라지지 않게 저장
    QueueNode *temp = q->front;
    element data = temp->data;
    
    if(is_empty(q)) error("스택이 비어있음");
    else{
        q->front = q->front->link;
        if(q->front == NULL) q->rear = NULL; //공백상태
        
        free(temp);
        return data;
    }
}

---

원형 단순 연결리스트

마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트

리스트 맨 뒤에도 O(1)에 삽입/삭제 가능 

 

head포인터가 마지막 노드를 가리키게끔 구성

-> head의 링크가 가리키는 것이 첫 번째 노드

 

ListNode* insert_first(ListNode* head, element data){
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    
    if(head == NULL){ //지금 만드는 노드가 첫 노드
        head = node;
        node->link = head; //자기 자신을 가리킴
    }
    else{
        //순서주의
        node->link = head->link; //노드가 head를 가리킴
        head->link = node; //노드가 head가 됨
    }
    
    return head;
}

ListNode* insert_last(ListNode* head, element data){
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->data = data;
    
    if(head == NULL){ //지금 만드는 노드가 첫 노드
        head = node;
        node->link = head; //자기 자신을 가리킴
    }
    else{
        //순서주의
        node->link = head->link; 
        head->link = node; 
        //앞에다 삽입하고 head가 날 가리키면 나 다음이 head가 됨
        head = node; 
    }
    
    return head;
}

 

원형큐

head를 rear로, head->link를 front로 사용

insert_last()로 enqueue(), delete_first()로 dequeue() 구현

---

이중 연결리스트

하나의 노드가 선행 노드와 후행 노드에 대한 두 개의 링크를 가짐

 

헤드노드: 데이터를 가지지 않음, 공백상태에서는 헤드 노드만 존재 

typedef struct DlistNode{
    element data;
    DlistNode *llink; //마지막 노드 가리킴
    DlistNode *rlink; //첫 번째 노드 가리킴
}DlistNode;

void dinsert(DListNode *before, element data){
    DListNode *newnode = (DListNode*)malloc(sizeof(DListNode));
    strcpy(newnode->data, data);
    
    newnode->llink = before;
    //순서주의
    newnode->rlink = before->rlink;
    before->rlink = newnode;
    newnode->rlink->llink = newnode;
}

void ddelete(DListNode *head, DListNode *removed){
    if(removed == head) return; //head는 지우지 않는다
    
    removed->rlink->llink =  removed->llink;
    removed->llink->rlink =  removed->rlink;
    
    free(removed);
}