[6장] 연결 리스트 I

연결 리스트에 대한 문제풀이 내용이다.
연결 리스트(Linked List)란?

 - 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

 - 메모리를 동적 할당을 기반으로 구현하여 데이터를 효율적으로 관리할 수 있는 장점이 있다. (배열 한계 극복)

 

[데이터 | 다음 노드의 주소] → [데이터 | 다음 노드의 주소] → [데이터 | 마지막 NULL]

연결 리스트의 구조 (출처: 위키백과)

구조체 리스트 노드를 생성하고 삽입하고 삭제하는 것부터 연습해보고,

리스트 탐색, 합병, 역순, 대체 및 삽입의 위치를 맨앞, 맨뒤 조정하여 함수를 구현해보자.

 

연결 리스트(주석과 함께 한줄씩 분석)

#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode{
 element data;                  // 데이타 (값)
 struct ListNode *link;         // 링크 (주소) 다음 노드의 data 의 주소가 저장 됨
} ListNode;

void error(char *message)
{
 fprintf(stderr, "%s\n", message); 
}

ListNode *create_node(element data, ListNode *link) 
{
 ListNode *new_node; 
 new_node = (ListNode *)malloc(sizeof(ListNode));      // 구조체 포인터 메모리 만큼 동적할당
 if(new_node == NULL) error("메모리 할당 에러");       // 생성된 노드가 NULL 이면 에러 메시지
 new_node->data = data; 
 new_node->link = link;                                        // 구조체포인터 new_node 의 data와 link
 return new_node;                                               // 그리고 생성된 노드를 리턴
}

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)  // 삽입 (리스트, NULL, creat_node(값, NULL))
{
 if (*phead == NULL)  // head의 주소가 NULL 이라면 // 앞에 삽입
 {
  new_node->link = NULL; // new_node 의 link가 NULL을 가리키게 하고
  *phead = new_node;  // head의 주소에는 new_node를 넣어준다
 }
 else if(p == NULL)  // 뒤에 삽입할 때
 {
  new_node->link = *phead; // new_node 의 link가 다음 노드의 주소를 가리킴
  *phead = new_node;  // head의 주소에 new_node를 넣어준다
 }
 else // 중간에 삽입할 때
 {
  new_node->link = p->link;
  p->link = new_node;
 }
}

void remove_node(ListNode **phead, ListNode *p, ListNode *removed) // 노드 제거 (&list, NULL, list)
{
 if( p == NULL )
  *phead = (*phead)->link; // head의 주소에 head의 주소의 link를 넣어준다
 else
  p->link = removed->link;
 free(removed);                  // 동적할당 해제
}

void display(ListNode *head)

{
 ListNode *p = head;
 if(head == NULL)   // 리스트가 비어 있을 때
  printf("List is empty\n");
 else{
  while(p != NULL) // 마지막 p가 NULL이 되는 순간 탈출
  {
   printf("%d->", p->data); // 값을 출력하고
   p = p->link;             // 다음 p의 주소를 가리킴
  }
  printf("\n");
 }
}

ListNode *search(ListNode *head, element x)
{
 ListNode *p;
 p = head;  // 시작 구조체 포인터 p 에 head 넣어줌
 while(p!=NULL) // p가 NULL 이 될 때 까지
 {
  if(p->data == x) return p; // 값이 탐색할 값과 같은지 확인 후 같으면 p 리턴
  p = p->link;    // 아니면 계속 다음 노드를 가리킴
  
 }
 return p;      // 결과적으로 p 리턴
}

ListNode *concat(ListNode *head1, ListNode *head2) // 두개의 리스트를 합병
{
 ListNode *p;
 if(head1 == NULL) return head2;   // 만약 첫번째 리스트에 아무것도 없으면 두번째 리스트만 리턴
 else if(head2 == NULL) return head1; // 두번째 리스트가 없으면 첫번째 리스트만 리턴
 else         // 둘 다 존재 하면
 {
  p = head1;       // p 에 list1 의head 넣고
  while(p->link != NULL)           // 다음 노드를 계속 가리키다가
   p = p->link;
  p->link = head2;     // NULL 이 되면 list2 의 head를 넣고
  
  return head1;      // 첫번째 리스트의 head를 리턴
 }
}

ListNode *reverse(ListNode *head){
 ListNode *p, *q, *r; // 순회 포인터로 p, q, r 사용
 p = head;            // 역순으로 만들 리스트
 q = NULL;            // 역순으로 만들 노드
 while(p != NULL){
  r = q;    // p q r 이 이동하면서 서로 역방향을 가리킴 q 의 앞과 뒤를 검사 해야해서 3개
  q = p;
  p = p->link;
  q->link =r;
 }
 return q;
}

void add_last(ListNode **head, ListNode *new_node) // 마지막에 삽입
{
 ListNode *pNode = *head;
 while(pNode->link != NULL) // 마지막까지 진행
 {
  pNode = pNode->link;
  
 }
 
 pNode->link = new_node; // 마지막 NULL 을 가리키던 링크가 새로운 노드를 받음
 
}

void add_first(ListNode **head, ListNode *new_node) // 첫번째에 삽입
{
 ListNode *pNode = *head; // 구조체 노드를 생성해 head의 주소를 넣어줌
 *head = new_node;   // head의 주소에 new_node 넣어줌
 (*head)->link = pNode;  // head 링크가 머리를 가리킴
 
}

void clear(ListNode **head) 
{
 ListNode *pNode= *head;
 ListNode *pPrev;
 
 if(pNode->link != NULL) // pNode의 주소가 NULL이 아니면
 {
  
  while(pNode->link != NULL) // 다음 노드로 넘겨주면서 Prev에 Node 넣어줌
  {
   pPrev = pNode;
   pNode = pNode->link;
  }
  
  free(pNode);    // Node 동적할당 해제
  pPrev->link = NULL;   // 받은 모든 요소들 NULL;
  
  clear(head);    // 재귀 head로 시작해서 모두 지움
 }
 else // 이미 다 지워져 있으면 그냥 동적할당 해제
 {
  free(*head);
  *head = NULL;
 }
}

void replace(ListNode *pNode, int pos, int data) // 어떤 list의 pos의 replace할 값
{
 int i;
 for(i=1;i<pos;i++)  // 대체할 값이 있는 노드까지 증가
 {
  pNode = pNode->link; // 계속 다음 노드의 주소를 가리킴
 }
 pNode->data = data;   // 그 노드의 값을 입력한 데이터로 변경 
 
}
int get_entry(ListNode *pNode, int pos) // list의 pos에 위치한 요소
{
 int i;
 for(i=1;i<pos;i++){
  pNode = pNode->link; // pos까지 계속 증가 시킨다음
 }
 
 return pNode->data;   // 그 값을 리턴
}

int is_empty(ListNode *head)
{
 if(head == NULL) // head 가 비어 있느냐
  return 1;
 
 return 0;
}

int get_length(ListNode *pNode) // 노드주소가 NULL이 될때까지 탐색 하면서 갯수 셈
{
 int i;
 for(i=1;pNode->link != NULL;i++, pNode=pNode->link){}
 return i;
 
}
void main(){
 ListNode *list1 = NULL, *list2= NULL;
 ListNode *p;
 insert_node(&list1, NULL, create_node(10, NULL));
 insert_node(&list1, NULL, create_node(20, NULL));
 insert_node(&list1, NULL, create_node(30, NULL));
 remove_node(&list1, NULL, list1);
 insert_node(&list2, NULL, create_node(60, NULL));
 insert_node(&list2, NULL, create_node(70, NULL));
 insert_node(&list2, NULL, create_node(80, NULL));
 display(list2);
 list1 = concat(list1, list2);
 display(list1);
 list1 = reverse(list1);
 display(list1);
 p = search(list1, 20);
 printf("탐색성공 : %d\n", p->data);
 
 printf("맨앞에 100추가\n");
 add_first(&list1, create_node(100, NULL));
 display(list1);
 
 printf("맨뒤에 200추가\n");
 add_last(&list1, create_node(200, NULL));
 display(list1);
 
 printf("리스트1의 2번째요소를 700으로 치환\n");
 replace(list1, 2, 700);
 
 display(list1);
 printf("리스트1의 2번째 요소 : %d\n", get_entry(list1, 2));
 printf("리스트1의 길이 : %d\n", get_length(list1));
 clear(&list1);
}

 

다음 7장에서는 심화학습으로 연결 리스트를 응용하여 스택과 큐를 구현해보자. (7장 링크)