자료구조(1)-링크드 리스트

리스트가 필요한 이유 - 배열은 한 번 선언하면, 그 크기를 변경할 수 없다. 동적인 상황에 대처가 불가능한 것이다. 그래서 유연하게 크기를 바꿀 수 있는 자료구조인 리스트가 필요하다! 

 

1. 링크드 리스트를 소개합니다.

 리스트 내의 각 요소는 노드(Node)라고 한다. 리스트는 이 노드를 연결해서 만든 자료구조이다. 

노드는 데이터 영역과, 다음 노드에 대한 포인터로 이루어져있다.

단일 연결 리스트사진(출처-위키백과)

회색 부분은 데이터를 담는 부분, 파란 색 부분은 다음 노드의 주소를 가리키는 포인터를 담는 부분이다. 저렇게 주렁주렁 엮는 것이 바로 링크드 리스트인 것이다.

 

리스트의 첫 번째 노트는 '헤드'라고 하고 마지막 노드는 '테일'이라고 한다. 

 

2. C언어로 표현된 링크드 리스트의 노드

/* 링크드 리스트의 노드 */
typedef struct Node
{
  int Data; // 데이터 필드
  struct Node *NextNode; // 다음 노드를 가리키는 포인터
} Node;

위는 데이터의 자료형이 int형인 것만 표현했으나, 필요에 의해 언제든지 바뀔 수 있다. typedef는 추후 선언이 좀 편하게 하기 위해 사용한 것이다.

 

3. 링크드 리스트의 주요 연산

총 다섯 가지이다. 노드 생성/소멸, 노드 추가, 노드 탐색, 노드 삭제, 노드 삽입 이다. 

 

먼저, 노드 생성/소멸이다.

/* 노드 생성 */
Node *SLL_CreateNode(ElementType NewData)
{	
  Node *NewNode = (Node*)malloc(sizeof(Node)); //node의 용량만큼 malloc한 다음, Node*의 자료형으로 바꿔준다.

  NewNode -> Data = NewData; //데이터 저장
  NewNode -> NextNode = NULL; //다음 노드에 대한 포인터는 NULL로 초기화

  return NewNode; //할당한 노드의 주소 반환
}

/* 노드 소멸 */
void SLL_DestroyNode(Node *Node)
{
  free(Node); //노드의 주소를 반환함으로써 노드를 소멸시킨다. 
}

다음으로 노드의 추가이다.