[Sieg]자료구조//링크드 리스트 - 3 - (노드 탐색, 제거, 삽입 및 카운트)

2편과 이어집니다.

1편 링크

2편 링크

노드 탐색

링크드 리스트가 가진 약점 중 하나. 배열이 인덱스를 이용해 원하는 정보에 접근하는 반면 링크드 리스트는 헤드에서 포인터를 이용해 하나하나 건너가야한다.

노드 탐색 함수 예

Node* SLL_GetNodeAt(Node* Head, int Location)

{

Node* Current = Head;    //Head에서 탐색을 시작

while( Current != NULL && (--Location) >= 0)    //현재 노드의 포인터가 NULL이 아니고 Location이 0보다 크거나 같음을 만족하는 동안

{

Current = Current->NextNode;    //포인터를 통해 다음 노드로 이동

}

return Current;    //while 종료 후 현재 노드를 반환

}

함수 적용

MyNode = SLL_GetNodeAt (List, 1); //두 번째 노드의 주소를 MyNode에 저장

노드 삭제

링크드 리스트 내 임의의 노드를 제거하는 연산. 삭제하려는 노드B를 찾은 후 다음 노드C를 이전 노드 A의 포인터에 연결하면 된다.

노드 삭제 함수 예

void SLL_RemoveNode(Node** Head, Node* Remove)

{

if(*Head == Remove)

{

*Head = Remove->NextNode;    //삭제할 노드가 헤드일 경우 다음 노드를 헤드로 지정

}

else

{

Node* Current = *Head;    //Head에서부터 탐색 시작

while (Current != NULL && Current -> NextNode != Remove)    //현재 노드의 포인터 값이 !=NULL, 다음노드가 !=Remove일 동안

{

Current = Current -> NextNode;    //다음 노드로 이동

}

if(Current != NULL)

Current->NextNode = Remove->NextNode;    //현재 노드가 NULL이 아니면 삭제할 노드의 포인터 값을 현재 노드에 입력

}

}

삭제할 노드의 앞 노드까지 이동 후 앞 노드의 포인터에 삭제한 노드의 포인터(즉, 다다음 노드의 주소)를 대입해준다.

함수 적용

SLL_RemoveNode (&List, MyNode); //위에서 탐색한 노드를 제거.

SLL_DestroyNode (MyNode); //제거한 노드를 메모리에서 완전히 소멸

노드 삽입

노드와 노드 사이에 새로운 노드를 끼워넣는 연산.

노드 삽입 함수 적용 예

void SLL_InsertAfter(Node* Current, Node* NewNode)

{

NewNode->NextNode = Current->NextNode;    //현재 노드가 가진 포인터 값을 새 노드의 포인터에 대입

Current->NextNode -> NewNode;    //새 노드의 주소를 현재 노드의 포인터에 대입

}

노드 갯수 세기

링크드 리스트 내에 존재하는 노드의 수를 세어 결과를 반환하는 함수로 만들 수 있다.

노드 갯수 세기 함수 적용 예

int SLL_GetNodeCount (Node* Head)

{

int Count = 0;

Node* Currernt = head;

while (Current != NULL)

{

Current = Current->NextNode;

Count++;

}

return Count;

}