[Sieg]자료구조//링크드 리스트 - 1 - (개요 및 구조체)

리스트?

리스트는 배열을 사용함에 있어 파일의 수를 예측할 수 없다는 점을 해결하기 위한 방법이다. 배열과 다르게 크기를 유연하게 다룰 수 있는 자료구조.

링크드 리스트(Linked List)

리스트를 구현하는 가장 간단한 방법.

리스트 내 각 요소를 노드(Node)라고 함. = 마디

리스트는 이러한 노드를 연결해서 만드는 것.

하나의 노드에는 데이터 영역과 다음 노드의 주소를 가리키는 포인터로 이루어져있다.

이러한 노드를 하나로 엮은 것이 링크드 리스트다.

리스트는 헤드와 테일을가지고 있다. 말그대로 리스트의 가장 첫 부분과 마지막 부분이다. 새로운 노드를 추가하더라도 새로운 노드가 테일이 되어 시작과 끝을 쉽게 알 수 있다.

중간에 노드가 사라지더라도 앞쪽 노드의 포인터를 소멸한 노드의 뒤쪽 노드의 주소 값으로 변경해주기만 하면 된다.

C언어로 표현한 노드 구조체

typedef struct tagNode

{

int Data;    //데이터 필드

struct Node* NextNode;    //다음 노드를 가리키는 포인터

}Node;

typedef를 사용해 구조체를 정의했다.

typedef로 구조체를 선언하면 키워드 없이 편리하게 사용할 수 있다.

Node NewNode;

이렇게.

주요 연산

링크드 리스트는 다섯가지 연산을 필요로 한다.

- 노드 생성 / 소멸

- 노드 추가

- 노드 탐색

- 노드 삭제

- 노드 삽입

이러한 자료구조를 유지하고 사용하기 위해서는 포인터를 수월하게 사용할 수 있어야한다.