[자료구조] 1. Linked List

1. 정의

Linked List는 data를 link를 이용해 저장하는 자료구조이다. 각각의 data와 link는 Node라고 불리는 Struct에 저장된다. 즉 Linked List는 자료가 저장된 Node를 연결시켜 구성할 수 있다. Linked Lint는 가장 일반적이고, 기초적인 자료구조로서 Stack, Queue와 같은 자료구조에 응용되기도 한다.

<The Concept of Linked List>

Linked List는 각각의 Node를 메모리에서 할당받아 사용하기 때문에, Array와 같이 선형적인 구조가 아니다. 따라서, Linked List는 Data의 논리적인 순서와 물리적인 순서는 다르게 된다.(Linked List의 Node가 메모리에 순서대로 할당되지 않는다. 메모리 어디든 할당받고 Link를 이용해서 연결하기만 하면 되기 때문.)

Linked List는 위와 같이 Node라는 것으로 이루어져있다. 각각의 Node는 데이터 필드(data field)와 링크 필드(link field)로 구성이 된다.

데이터 필드(data field)는 원소의 값을 저장한다. 저장하고자 하는 자료형은 사용자가 정해주기 나름이다. int, float와 같은 타입부터 struct 타입까지 가능해 어떤 자료도 담을 수 있다. 링크 필드(link field)는 다른 노드의 주소를 저장한다. 일반적으로 포인터 변수를 사용하여, 노드의 주소를 가리킨다. 링크 필드의 경우, 기본적으로 1개이지만, 여러 개를 만들어 다수의 노드를 연결할 수도 있다.

Linked List에서 자료의 끝을 지정하는 법은 링크 필드가 가리키는 link를 NULL로 지정하는 것이다.

2. 장단점

1) 장점

- Data의 Insertion, Deletion이 쉽고 빠르다.

- 필요한 메모리를 동적할당해 사용하므로, 불필요한 메모리 낭비가 없다.

2) 단점

- 원하는 data의 Search가 느리다.(Array는 연속적인 메모리를 사용하는 반면, LInked List는 그렇지 않다.)

3. 종류

- Singly Linked List

Singly Linked List에서의 Node는 Data field와 Next field를 가진다. Data field는 저장할 data가 있으며, Next field에는 다음 Node를 가리키는 주소가 있다. 단방향 탐색만이 가능하며, 가장 끝에는 Null 포인터가 들어가 끝임을 알려준다.

- Doubly Linked LIst

Doubly Linked List에서의 Node는 Previous field, Data field, 그리고 Next field가 있다. Singly Linked List와 동일하지만, Previous field는 이전 Node의 주소가 있다. 즉 양방향 탐색이 가능하다. Doubly Linked List는 양쪽 끝 모두에 Null 포인터를 사용한다.

- Circular Linked List

Circular Linked List에서의 Node는 Singly Linked List의 Node와 사용되는 field가 동일하다. 다만, Circular Linked List의 끝은 Null 포인터가 아니라, Head 포인터를 가리킨다. 끝이 존재하지 않는 구조이므로, Ciruclar Linked List라 일컫는다. Singly Linked List뿐만 아니라 Doubly Linked List 또한 Ciruclar Linked List로 구현이 가능하다.

4. 구현

#include<stdio.h>
#include<stdlib.h>
 
/*Linked List에 사용할 Node*/
typedef struct _node *nodeptr;
typedef struct _node{
    int data;
    nodeptr link;
}node;
 
/*Linked List의 제일 앞(Head)*/
nodeptr Head=NULL;
 
void InsertNode(int);
void DeleteNode();
 
int main(void){
    int n,i,temp;
    nodeptr search;
 
    printf("Input the number of data : ");
    scanf("%d",&n);
 
    i=0;
 
    while(i!=n){
        scanf("%d",&temp);
        
        InsertNode(temp);
 
        i++;
    }
 
    search=Head;
    while(search->link){
        printf("[%d] -> ",search->data);
        search=search->link;
    }
    printf("[%d] END\n", search->data);
 
    while(Head){
        DeleteNode();
    }    
    printf("\nDelete Complete.\n");
 
    return 0;
}
 
void InsertNode(int data){
    nodeptr tempnode,search=Head;
    
    tempnode=(nodeptr)malloc(sizeof(node));//임시 Node 생성
    tempnode->data=data;
    tempnode->link=NULL;
 
    if(!Head) Head=tempnode;//Head가 Null인 경우 link가 존재하지 않으므로, 바로 Insert.
    else{
        while(search->link) search=search->link;//Link가 Null인 Node를 탐색
        search->link=tempnode;
    }
 
    return;
}
 
void DeleteNode(){
    nodeptr search=Head;
 
    if(!Head){
        //Do Nothing
    }
    else if(!Head->link){//Head Node 하나만 존재하는 경우
        free(Head);
        Head=NULL;
    }
    else{/*일반적인 경우, Node의 다음 Node의 link가 Null인 것을 탐색.
         (다음 Node를 free시키고, Node의 link를 Null로 하기 위함.)*/
        while(search->link->link) search=search->link;
        free(search->link);
        search->link=NULL;
    }
    return;
}