리스트 간단 설명 요약

링크드 리스트

 

- 리스트를 구현하는 여러가지 기법중 가장 간단한 방법

 

- 리스트에서 마디를 노드라 한다.

 

- 리스트의 첫번째 노드 : 헤드 , 마지막 노드 : 테일

 

======================================================================

 

C언어로 표현하는 링크드 리스트의 노드

 

struct Node

{

int Data; /* 데이터 필드 */

 

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

};

 

======================================================================

 

링크드 리스트를 구축하고 자료를 사용하기 위한 필요연산은

 

- 노드 생성/소멸

- 노드 추가

- 노드 탐색

- 노드 삭제

- 노드 삽입

 

여기서 노드탐색은 구축되어있는 데이터를 활용하기위한 연산이고, 그외4가지는  자료구조를 구축하기 위한 연산

 

======================================================================

 

c언어로 작성된 프로그램은 세가지 종류의 메모리 영역을 가진다.

 

- 정적 메모리 : 전역변수나 정적변수가 저장

 

- 자동 메모리 : 지역변수가 저장

 

- 자유 저장소 

 

 

여기서 정적메모리는 프로그램이 종료될때 해제되는 영역

 

자동메모리는 코드블록이 끝나는 곳에서 자동으로 메모리를 해제

 

자동메모리는 스택 구조로 이루어져 있다.

 

======================================================================

 

STL_ : Singly Linked List 의 약자

 

======================================================================

 

노드 생성  - 함수 : STL_CreateNode();

 

Node* NewNode = (Node*)malloc(sizeof(Node));

 

malloc 함수는 sizeof 연산자가 측정한 노드의 크기만큼 자유저장소에 할당한 후

 

NewNode에 그 메모리주소를 저장한다.

 

ex)  /* 노드 생성 */

 

Node* STL_CreateNode(ElementType NewData)

{

Node* NewNode = (Node*)malloc(sizeof(Node));

NewNode->Data=NewData;  /* 데이터를 저장한다 */

NewNode->NextNode = NULL; /* 다음 노드에 대한 포인터는 NULL로 초기화한다 */

 

return NewNode; /* 노드의 주소를 반환한다 */

}

 

 

노드 소멸  - 함수 : STL_DestroyNode();

 

void STL_DestroyNode(Node* Node)

{

free(Node);

}

 

 

노드 추가  - 함수 : STL_AppendNode();

 

링크드 리스트 테일 노드 뒤에 새로운 노드를 만들어 연결하는것이다.

 

 

노드 탐색   - 함수 : STL_GetNodeAt();

 

장점 : 배열이 인덱스를 이용하여 즉시 원하는  요소를 취할 수 있게 한다.

 

단점 : 헤드부터 시작해서 다음노드에 대한 포인터를 징검다리삼아 차근차근

노드의 수를 세어나가야만 원하는 요소에 접근할 수 있다.

 

 

노드 삭제   - 함수 : STL_RemoveNode();

 

임의의 노드를 제거하는 연산.

삭제하고자 하는 노드를 찾은 후 해당 노드의 다음 노드를 이전 노드의

NextNode 포인터에서 제거하면 된다.

 

그리고 삭제한 노드는 달리 쓸 곳이 없다면 STL_DestroyNode() 함수를 이용해

소멸 시키면된다.

 

 

노드 삽입   - 함수 : STL_InsertAfter();

 

노드 삽입은 노드와 노드 사이에 새로운 노드를 끼워넣는 것이다.

 

 

노드 개수 세기  - 함수 : STL_GetNodeCount()