[C/C++자료구조] 연결리스트

List by AB from the Noun Project

 

연결리스트에 대해 알아보려 합니다.

 

연결리스트로는 크게 배열, 단방향, 양방향리스트로 구현 가능한데요.

각각의 구현과 장단점을 정리해보고자 합니다.

 

#연결 리스트란

메모장에 할 일이나 쇼핑목록을 나열하듯 데이터를 저장하는 자료구조이며, 이들을 연결해 삽입과 삭제, 탐색을 할 수 있습니다.

 

#배열 리스트

배열 리스트의 장점은 어느 위치에 저장되어 있는지 index(위치)를 알고 있다면 바로 접근해서 데이터를 가져올 수 있지만,

배열의 크기를 처음에 지정해야 하므로, 적정한 배열의 크기를 정해야 하는 단점이 있습니다. 또한 삭제나 삽입을 할 때 모든 배열을 앞으로나 뒤로 방문하여 밀거나 당겨야 하는 상황에 불필요한 메모리 낭비나, 탐색을 할 수 있습니다.

#include<stdio.h>
int arr[10];
int cnt=0;
void push_back(int data){
	arr[cnt]=data;
	cnt++;
}
void push_front(int data){
	for(int i=cnt; i>=1; i--){
		arr[i]=arr[i-1];
	}
	arr[0]=data;
	cnt++;
}
void erase(int data){
	int temp=0;
	for(int i=0; i<cnt; i++){
		if(arr[i]==data){
			temp = i;
			break;
		}
	}
	for(int j=temp; j<cnt; j++){
	arr[j]=arr[j+1];
	}
	cnt--;
}
int main(){
	push_back(1);
	push_back(3);
	push_front(5);
	push_front(7);
	push_back(9);
	erase(3);
	push_back(11);
	for(int i=0; i<cnt; i++){
		printf("%d ", arr[i]);
	}
	return 0;
}

위와 같이 배열을 선언해서 push_back과 push_front를 구현했음을 알 수 있습니다.위와 같이 배열을 선언해서 push_back과 push_front, erase를 간단하게 구현했음을 알 수 있습니다.
 결과는 7 5 1 9 11
 erase는 원하는 숫자 하나를 삭제하는 함수이지만, 배열을 사용했기 때문에 특정 배열 위치를 삭제하고 리스트를 수정하는 것도 가능하다고 생각합니다. 하지만 앞과 뒤가 아닌 원하는 위치에 삽입과 삭제가 비효율적입니다.

#단방향 연결리스트

단방향 연결리스트는 구조체와 포인터를 이용하여 특정 지점에 노드를 추가 삭제 할 수 있으며 추가와 삭제를 할 때마다 노드를 동적으로 할당 받아 배열과 다르게 동적으로 크기를 지정할 수 있습니다.
 처음과 끝 노드를 head와 NULL을 이용하여 구현합니다.

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
    int data;
    struct Node *next;
} Node;
Node *head;

void push_front(Node *root, int data){
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->next = root->next;
    root->next = node;
}

void push_back(Node *root, int data){
    Node *cur = head->next;
    while(cur!= NULL){
        Node *next = cur->next;
        if(next == NULL){
            Node *node = (Node*) malloc(sizeof(Node));
            cur->next = node;
            node->data = data;
            node->next = NULL;
        }
        cur = next;
    }
}
void freeAll(Node *root){
    Node *cur = head->next;
    while(cur != NULL){
        Node *next = cur->next;
        cur = next;
    }
}

int main(){
    head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    push_front(head, 1);
    push_back(head, 3);
    push_back(head, 5);
    Node *cur = head->next;
    while(cur!=NULL){
        printf("%d ", cur->data);
        cur=cur->next;
    }
    freeAll(head);
    return 0;
}

 

위와 같이 push_front와 push_back을 구현했음을 알 수 있습니다. 결과는 1 3 5

 

다음 시간에는 양방향 연결리스트에 대해 알아보겠습니다.

 

<본 코드는 fastcampus 컴퓨터공학 올인원패키지 나동빈강사의 자료구조 강좌의 코드를 참고 후 추가하여 작성되었음을 알립니다.>