알고리즘 - 연결리스트

단순 연결 리스트

Node 구조체

• Node 구조체는 연결 리스트의 한 요소인 노드를 정의한다.
• 연결 리스트는 정수를 데이터로 가지므로 정수형 변수 value와 링크 next만 멤버로 갖는다.
• Node형 포인터 head는 연결리스트의 진입점이다.
• head의 링크(head->next)가 NULL이라는 것은 머리 외에 실제 데이터를 가지는 노드는 없다는 뜻이며 이는 곧 연결 리스트가 비어있다는 뜻이다.
  

노드의 삽입

• 노드는 자신과 연결된 노드의 정보를 가지고 있으므로 물리적 메모리 이동 없이 링크만 조작하여 리스트의 중간에 새로운 노드를 쉽게 삽입할 수 있다.

• 1, 2, 3 세 개의 노드가 있는 상태에서 노드 2 다음에 노드 4가 삽입되는 가장 일반적인 경우의 과정
  
  ① Node 구조체를 새로 할당하여 New 노드를 만들고 이 노드의 value에 4를 대입. 노드 4의 next는 현재 쓰레기값을 가지고 있는 상태.
  
  ② 새로 만든 노드 4의 링크에 노드 3의 번지를 대입 (New->next = Target->next).
  노드 4가 노드 3 앞에 위치하도록 연결.
  노드의 3의 번지는 바로 앞에 있는 노드 2의 링크에서 구할 수 있는데 노드 2의 값을 바꾸기 전에 먼저 읽어야 한다.
  
  ③ 노드 2 링크에 노드 4를 대입(Target->next=New). 노드 4가 노드 2 다음에 위치하도록 연결한다.

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

struct Node
{
	int value;
	Node* next;
};

Node* head;

Node* InsertNode(Node* Target, Node* aNode)
{
	// Target은 현재 노드
	// aNode는 추가할 노드

	Node* New = (Node*)malloc(sizeof(Node));
	*New = *aNode; // Temp의 정보가 복사가 됐다.

	New->next = Target->next;
	Target->next = New;
	return New;
}

void main()
{
	head = (Node*)malloc(sizeof(Node));
	head->next = NULL;

	Node* Now;
	Node Temp;

	Now = head;

	for (int i = 0; i < 6; i++)
	{
		Temp.value = i + 1;
		Now = InsertNode(Now, &Temp);
	}

	for (Now = head->next; Now; Now = Now->next) // Now; : 주소값이 null이 아닐동안 실행. 마지막 주소값은 null이므로.
	{
		printf("%d\t", Now->value); // \t : 한 tab
	}
}

노드의 삭제

• 노드를 삭제하는 방법도 링크를 조작하는 것이다.
• 앞쪽 노드를 찾지 못하므로 노드 자체를 삭제할 수 없고 노드의 뒤쪽만 삭제할 수 있다.
  
• 노드 2를 제거하려면? Target->next = Del->next함으로써 Del을 리스트에서 제외시킨다.
• Del의 메모리는 free 함수를 통해 물리적으로 제거한다.