[프로그래밍/알고리즘] 링크드 리스트 정의, 종류

1.링크드 리스트

노드(node)와 링크(link)로 구성이 된다

노드 : 실제 정보를 담고 있는 단위

링크 : 인접 노드의 위치(주소)를 저장하고 순서를 유지하는 연결고리

배열 : 정적인 자료구조, 연속된 메모리 공간을 차지

연결리스트 : 동적인 자료구조 수시로 할당과 해제되기 때문에 연속된 메모리 공간이 아니다

- 장점 : 메모리 관리가 쉽다

           동적인 자료구조 이므로 실행중에 얼마든지 크기를 조절할수 있다(삽입과 삭제가 용이)

- 단점 : 구현하기가 어렵다

[연결리스트의 종류]

1. 단순 연결 리스트

2. 환형 연결 리스트

3. 이중 연결 리스트

4. 이중 환형 연결 리스트

단순 연결 리스트가 가장 많이 사용이 된다.

[연결리스트]

1. 초기화

#include<stdio.h>

#include<stdlib.h>

typedef struct list_node* list_pointer;

typedef struct list_node

{

      int data;

      list_pointer next;

};

void Init();                                                     // 초기화 함수

list_pointer head;                                           // 전역으로 머리와

list_pointer tail;                                              // 꼬리를 선언

void Init()

{

     head = (list_pointer)malloc(sizeof(list_pointer));

     tail = (list_pointer)malloc(sizeof(list_pointer));

     head->next = tail;                              // 머리 다음을 꼬리로 연결

     tail->next = tail;                                 // 꼬리의 끝은 꼬리이다. 

}

2. 맨뒤에 입력하기

void Insert(int key);                                 // 입력함수(맨뒤에 삽입)

void Insert(int key)

{

     list_pointer insert;

     list_pointer current;

     insert = (list_pointer)malloc(sizeof(list_pointer));

     current = head;                                  // current(포인터) 에 head 주소 대입.

    while(current->next != tail)                   // 꼬리 바로 앞까지 가라는말.

         current = current->next;                  

    current->next = insert;                         // current는 현재 꼬리 앞인데 그담을 insert에 연결

    insert->next = tail;                               // insert(입력데이터)를 꼬리에 연결

    insert->data = key;                              // insert에 값을 넣어줌.

}

- tail 바로 앞에 있는 노드에 새로 입력할 노드를 연결. 그리고 그 노드는 tail과 연결해서 새로 

  입력할 값이 꼬리 앞으로 가게 되는 원리이다. main 에서 insert(10)을 넣으면 10 이란 데이터가 

  맨뒤에 저장이 된다.  그담 insert(20)을 하면 10 다음에 20이 저장되고 그담이 tail....

3. 출력하기

void print(); 

void print()

{

     list_pointer p = head;

     int num = 0;

    while(p->next != tail){                                  // 꼬리가 아니라면 

          num++;

          p = p->next;

          printf("%d node = %d \n",num,p->data);   

    }

}

- 꼬리를 만날때까지 연결된 값을 차례로 출력한다.

4. 검색하기

list_pointer Find(int key);                  // 리턴형이 node 이다 찾은 node를 리턴해준다. 

list_pointer Find(int key)

{

     list_pointer search = head->next;   

     while(search->data != key && search != tail)

          search = search->next;

     return search;

 }

-> 데이터 값으로 노드를 찾는다. 호출할때 list_pointer temp 란 변수를 만들어 

    temp = Finde(10);    10 이란 데이터가 있는 node를 temp 에 리턴해준다.

5. 검색해서 얻은 노드 뒤에 데이터 삭제

int Delete(list_pointer find)              

{

      list_pointer del;

 

      if(find->next == tail)

          return 0;

      del = find->next;                              // 검색해서 얻은 노드 다음을 연결

      find->next = find->next->next;           // 검색한 노드의 다음은 다음(삭제대상) 다음을 연결

      free(del);                                        //  삭제

      return 1;

}

6. 검색해서 얻은 노드 뒤에 데이터 삽입

void Find_Insert(int key,list_pointer find)   

{

     list_pointer current;

     current = (list_pointer)malloc(sizeof(list_pointer));

     current->data = key;

     current->next = find->next;

     find->next = current;

}

7. 입력한 키값 들어 있는 노드 삭제

int Find_del(int key)         

{

     list_pointer temp;

     list_pointer search;

     temp = head;

     search = temp->next;

     while(search->data != key && search != tail)

     {

          temp = temp->next;

          search = temp->next;

     }

     if(search != tail)

     {

            temp->next = search->next;

            free(search);

            return 1;

     }

 

     else

           return 0;

}

8. 입력한 키 값 앞에 데이터 삽입

void Find_PreInsert(int key, int find)     

{

     list_pointer front;

     list_pointer search;

     list_pointer current;

     front = head;

     search = front->next;

    while(search->data != find && search != tail)

    {

         front = front->next;

         search = front->next;

    }

    if(search != tail)

    {

         current = (list_pointer)malloc(sizeof(list_pointer));

         current->data = key;

         front->next = current;

         current->next = search;

    }

 }

9. 모두 삭제

void All_Free()

{

     list_pointer search;

     list_pointer temp;

     temp = head->next;

     while(temp != tail)

     {

          search = temp;

          temp = temp->next;

          free(search);

     }

     head->next = tail;

}