연결 리스트 1

6장 연결 리스트 1

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

리스트

특징

• 항목들이 차례대로 저장되어 있다.
• 항목들은 순서 또는 위치를 가진다.
• 스택과 큐도 넓게 보면 리스트의 일종이다.
• 리스트는 집합하고 다르다.(집합은 항목 간에 순서의 개념이 없다.)
• 배열과 연결 리스트를 이용하여 구현한다.

배열로 구현한 리스트

• 간단하게 구현
• 속도가 빠름
• 크기가 고정
• 접근 시간 복잡도 : O(1)
• 삽입, 삭제 연산 : 최악의 경우 O(n) / 맨 끝에 삽입하는 경우 O(1)

연결 리스트

• 정의 : 데이터들이 메인 메모리상의 어디에나 흩어져서 존재할 수 있고, 이런 물리적으로 흩어져 있는 데이터들을 서로 연결하여 하나로 묶는 방법
• 포인터 사용
• 배열 리스트에서 가장 문제가 되는 중간에 삽입하는 문제를 쉽게 해결할 수 있다.

연결 리스트의 구조

• 노드(node) :
  메모리 어디에나 있을 수 있으며, 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용
  데이터 필드 + 링크 필드로 구성
• 연결 리스트에서는 연결 리스트의 첫번째 노드를 알아야 만이 전체의 노드에 접근 가능
• 첫 번째 노드를 가리키고 있는 변수 : 헤드 포인터
• 마지막 노드의 링크 필드 : NULL(더이상 연결된 노드가 없다는 것을 의미)
• 노드는 필요할 때마다 malloc()을 이용하여 동적으로 생성
• 연결 리스트의 종류 : 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트

단순 연결 리스트

• 페이지 길이가 길어지므로, 여기서는 단순 연결 리스트 코드만 소개해보겠다.
• 노드들이 하나의 링크 필드를 가지며, 이 링크 필드를 이용하여 모든 노드들이 연결, 마지막 노드의 링크 필드 값은 NULL

#include<stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode{
  element data;
  struct ListNode *link;
} ListNode;

//첫번째 삽입
ListNode* insert_first(ListNode *head, int value)
{
  ListNode *p = (ListNode *)malloc(sizeof(ListNode));
  p->data = value;
  p->link = head;
  head = p;
  return head;
}

//삽입
ListNode* insert(ListNode *head, ListNode *pre, element value)
{
  ListNode *p = (ListNode *)malloc(sizeof(ListNode));
  p->data = value;
  p->link = pre->link;
  pre->link = p;
  return head;
}

//첫번째 삭제
ListNode* delete_first(ListNode* head)
{
  ListNode *removed;
  if (head == NULL)
    return NULL;

  removed = head;
  head = removed->link;
  free(removed);
  return head;
}

//삭제
ListNode* delete(ListNode *head, ListNode *pre)
{
  ListNode *removed;
  removed = pre->link;
  pre->link = removed->link;
  free(removed);
  return head;
}

//출력
void print(ListNode *head)
{
  for (ListNode *p = head; p != NULL; p = p->link)
    printf("%d->", p->data);
}