연결리스트 - 단순연결리스트 with C

Linked List

링크를 가진 노드들의 순열이다. 배열은 메모리와 밀접하게 연관이 있지만 연결리스트는 무조건적으로 연관되지 않는다. 삽입과 삭제가 비교적 간단하고 최대 크기가 정해져 있지 않다. 포인터로 구현할 수 있으며 노드는 데이터와 포인터로 나눌수 있다.

연결리스트

 head로 시작하여 노드들의 연속을 볼 수 있다. 노드에는 데이터를 저장하는 데이터부와 다음 노드를 지정하는 포인터로 구분한다. 포인터에는 다음 노드의 시작 주소를 가리키게 된다.(구조체의 주소는 구조체의 시작 주소와 같다.) C에서 구조체를 이용하여 노드를 구현하고 포인터는 구조체 포인터로 지정한다. 마지막 노드는 다음 노드가 없으므로 NULL 값으로 지정된다.

 

노드 구성 및 생성

노드 구조체

struct node{
	int data;
	struct node *next;
};

 노드는 구조체로 정의하여 데이터로 int형 자료형을 저장하는 형태로 정의하였다. 보통은 이렇게 구성하나 편의를 위해 사용자 정의 자료형을 이용하여 노드를 생성할 것이다.

typedef struct node* node_pointer;
typedef struct node{
	int data;
	node_pointer next;
}node;

노드 생성

노드 생성 시 응용프로그램 동작중에 메모리를 할당받아 사용한다. 동적으로 할당되어 사용되며 메모리의 힙 영역에 할당하게 된다. 힙 영역은 동적 할당을 위해 비워두는 일종의 여유공간이며 힙 영역 역시 무제한으로 사용할 수 있는 것은 아니다.

node_ptr=(node_pointer)malloc(sizeof(node));

 연결리스트의 특성상 미리 할당되지 않고 구간이 정해져 있지 않다. python이나 Java 같은 언어를 자동으로 동적 할당을 할 수 있지만 C나 C++ 같은 경우 직접 개발자가 메모리를 관리하기 때문에 동적 할당 선언을 해야 한다. malloc함수를 사용하여 동적 할당을 할 수 있다.

노드 삽입 삭제

• 노드 삽입

 연결리스트의 삽입은 간단하게 이뤄진다.

맨 끝에 노드를 삽입하는 경우

연결리스트-삽입-1-1

연결리스트-삽입-1-2

A노드의 포인터 NULL값을 B노드의 주소로 지정한다. 끝 노드에 추가만 하면 되기에 간단하다.

노드 중간에 삽입하는 경우

연결리스트-삽입-1-3

연결리스트-삽입-1-4

 노드 중간에 삽입할 경우 기존의 삽입 중간에 링크를 끊고 삽입될 노드와 링크해줘야 한다. A노드의 포인터를 C의 주소 값으로 변경하고 C는 B의 주소로 입력한다.

• 노드 삭제

노드 삭제는 매우 간단한다.

연결리스트-노드삭제-1

연결리스트-삭제-2

 삭제할 노드의 이전 노드를 다음 노드의 주소를 가리키게 하면 된다. 위 과정을 보면 노드는 C노드의 주소 값으로 변경하고 B는 해제된다. 이때 동적으로 할당된 메모리는 free() 함수를 이용하여 풀어준다.

노드 검색과 출력

 노드 검색

  노드를 차례로 순회하면서 해당 노드를 검색한다.

 노드 출력

  첫 노드부터 순회하며 노드를 출력한다.

 

C로 구현하는 단순 연결리스트

노드 생성

typedef struct linked_list *node pointer;
typedef struct linked_list{
	int data;
	node_pointer next;
}linked_list;

node_pointer ptr;
ptr=(node_pointer)malloc(sizeof(linked_list));
ptr->next=NULL;
ptr->data=4;

노드 삽입

ptr은 노드를 가리키는 포인터

void insert_node(node_pointer ptr,linked_list node){
	if(ptr){
		node->next=ptr->next;
		ptr->next=node;
	}else{
		node->next=head;
		head=node;
	}
}

노드 삭제

void delete_node(node_pointer ptr,linked_list node){
	if(ptr){
		ptr->next=node->link;
		p->link=p->link->link;
	}else{
		head=head->link;
	}
	free(node);
}

연결리스트 정리

 연결리스트중 단순 연결리스트는 다음 노드를 가리킴으로써 리스트를 만든다. 정해지지 않은 길이의 리스트에 효율적으로 동작한다. 연결리스트를 이용하여 큐, 스택, 트리등을 구현할 수 있다. 연결리스트는 이러한 것 외에도 컴퓨터 동작에 있어서 이해가 필요한 부분이다. 연결리스트는 이외에도 활용이 다양해 매우 중요하다. 연결 리스트 중에는 이중연결리스트도 존재한다. 이중 연결 리스트의 노드는 이전 노드와 다음 노드의 주소 정보를 둘 다 가지고 있기 때문에 삽입 삭제가 복잡해지지만 이전 노드로 돌아갈 수 있다는 장점이 있다.