[자료구조] Linked list 1

2023-03-28 4 분 소요

자료구조

Linked list 2

Linked list는 차례로 배열된 일련의 데이터 항목으로, 각 항목은 링크로 다음 항목에 연결된다.

배열에 비해 추가/삭제가 용이하며 동적 할당을 기반으로 한 리스트이기 때문에 크기를 미리 지정할 필요가 없다는 장점이 있지만 특정 데이터를 찾기 위해서는 순차 탐색을 하므로 탐색 속도가 느린 단점이 있다.

Linked list의 기본 Node Class

“node” class

c++에서의 node class 이다.

class node
{
	public:
		typedef double value_type;
	private:
		value_type data_field;
		node* link_field;
		...
}

head_ptr, tail_ptr

프로그램은 포인터 변수 head_ptr을 사용해서 앞 노드를 추적할 수 있다. 또한 tail_ptr은 리스트의 마지막 노드에 대한 포인터이다.

즉 head_ptr 및 tail_ptr은 노드가 아니라 노드에 대한 포인터이다.

head_ptr, tail_ptr의 선언

class node
{
	public:
		typedef double value_type;
	private:
		value_type data_field;
		node* link_field;
		...
};
node* head_ptr;
node* tail_ptr;

헤드 포인터에 NULL을 저장하여 빈 list를 나타낸다.

head_ptr = NULL;
	//const NULL from cstdlib

node constructor

노드 생성자 :

node(
	const value_type& int_data = value_type(),
	const node* init_link = NULL)
{
	data_fild = init_data;
	link_field = init_link;
}

node member funtion definitions

노드 멤버 함수 정의 :

class node
{
	public:
		node ( ... ); // 윗부분
		void set_data(const value_type& new_data) ; //데이터 변경
		void set_link(node* new_link) ; // 링크 변경
		value_type data( ) const ; // 데이터 찾기
		const node* link( ) const ; // 링크 찾기1
		node* link( ) ; // 링크 찾기2
}

일반 포인터 node*를 리턴하는 함수

예제: head_ptr -> 10 -> 7 <- second 라는 예제에서 7을 9.2로 변환

node* link(){return link_field;}
node *second = head_ptr->link();
// ->은 Member selection operator로 (*head_ptr).link()와 같다.
second->set_data(9.2); // 7을 9.2로 값 변경!

const 포인터 node*를 리턴하는 함수

위 예제와 동일하다.

const node* link() const {return link_field n;}
const node* second = head_ptr->link();
// ->은 Member selection operator로 (*head_ptr).link()와 같다.
second->set_data(9.2); // Error!! const이기 때문에 변경 불가능

Linked List Toolkit

Linked list의 Operations들을 하나씩 알아보자

Length

먼저 길이 함수다. 이는 링크드 리스트의 길이를 계산해주는 연산자이다.

헤드_ptr -> 10 -> 15 -> 7(null) 라는 리스트가 있다. 여기서 cursor가 리스트를 쭉 돌면서 수를 카운트해 answer에 값이 저장되게 하면 된다.

size_t list_length(const node* head_ptr)
{
	size_t answer = 0 ;
	const node *cursor ;
	for(cursor=head_ptr; cursor!=NULL; cursor=cursor->link())
		++answer ;
	return answer ;
};

Insert head

다음은 insert다. 먼저 head부분에 insert하는 함수를 알아보자.

예제 : linked list는 head_ptr -> 10 -> 15 -> 7(null) 라는 리스트가 있다. 추가하려는 entry값은 13이다. 과정은 다음과 같다.

1. 값은 entry에 있는 값을 가지고 링크는 head_ptr의 링크를 따르는 새 노드를 만든다.

2. head_ptr의 링크를 새 노드로 변경한다.

다음과 같이 한줄로 코드를 짤 수 있다.

void list_head_insert(node*& head_ptr, const node::value_type& entry)
{
	head_ptr = new node(entry, head_ptr) ;
}

Insert

이번엔 head에 insert하는 것이 아닌 리스트 특정 위치에 노드를 insert해보자.

예제 : head_ptr -> 10 -> 15 -> 7(null) 라는 리스트가 있다. 15와 7사이에 값이 13인 entry를 추가하고자 한다. previous_ptr은 -> 15인 노드다. 과정은 다음과 같다.

1. 새 노드를 생성한다.

2. entry값을 노드에 넣는다.

3. 노드의 링크를 previous_ptr->link()로 한다.

4. previos_ptr->link()가 7이 아닌 새 노드로 가리키도록 한다.

코드는 다음과 같다.

void list_insert(node* previos_ptr, const node::value_type& entry){
	node* insert_ptr;
	insert_ptr = new node;
	insert_ptr->set_data(entry);
	insert_ptr->set_link(previous_ptr->link());
	previous_ptr->set_link(insert_ptr);
}

위 코드를 한줄로 정리할 수 있다!

void list_insert(node* previos_ptr, const node::value_type& entry){
	previous_ptr->set_link(new node(entry, previous_ptr->link()));
}

Search

searcch는 링크드 리스트에서 데이터 항목을 검색하고 발견되면 데이터 아이템을 포함하는 첫번째 노드에 대한 포인터를 리턴하는 함수다.

head_ptr -> 10 -> 15 -> 7(null)이라는 링크드 리스트가 있다. 여기서 15를 찾고 싶다면 찾고자 하는 데이터 아이템을 target으로 두고 값은 15로 한다. 또한 임시 curser포인터를 생성한다. 과정은 다음과 같다.

node* list_search(node* head_ptr, const node::value_type& target)
{
	node* cursor;
	for(cursor=head_ptr; cursor !=NULL; cursor=cursor->link())
		if(target == cursor->data())
			return cursor;
	return NULL;
}

Locate

링크드 리스트에서 노드의 위치를 찾고 해당 노드의 대한 포인터를 리턴하는 함수다.

head_ptr -> 10 -> 15 -> 7(null) 의 링크드 리스트가 있다. 여기서 2번째(15)를 찾고 싶으면 position 포인터를 이용해 2의 값을 준다. 자세한 과정은 다음과 같다.

node* list_locate(node* head_ptr, size_t position);
{
	node* cursor;
	size_t i;
	assert(0 < position); //precondition으로 error방지
	for(cursor=head_ptr,i=1; (cursor !=NULL && i<position); ++i)
		cursor = cursor->link();
	return cursor;
}

Copy

복사 : 링크드 리스트에서 헤드와 테일 포인터를 모두 포함하는 링크드 리스트 복사본을 만드는 함수이다.

우선 위와 같은 예제가 있고 순서는 다음과 같다.

1. head_ptr 및 tail_ptr을 NULL로 설정.

2. source가 비어있으면 리턴한다.

3. 헤드에 첫번째 노드를 할당하고 헤드 포인터와 테일 포인터가 이를 가이키도록 한다.

4. 기존 리스트에서 2번째 노드로 이동하고 해당 노드를 복사해 온다.

5. 새 리스트의 꼬리에 복사해온 노드를 insert하고 이를 기존 리스트의 끝까지 반복한다.

코드

void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
{
	head_ptr = NULL;	tail_ptr = NULL;
	if(source_ptr==NULL)
		return;
	list_head_insert(head_ptr,source_ptr->data());
	tail_ptr = head_ptr;

	source_ptr = source_ptr->link();
	while(source_ptr != NULL){
		list_insert(tail_ptr,source_ptr->data());
		tail_ptr = tail_ptr->link();
		source_ptr=source_ptr->link();
	}
}

Remove head

링크드 리스트에서 1번째 노를 삭제하는 함수다.

1번째 노드에 대한 remove_ptr이라는 임시 포인터를 설정해 시작한다.

1. remove_ptr을 설정

2. head_ptr = remove_ptr->link();

3. delete remove_ptr; //노드의 메모리를 힙으로 리턴한다.

여기서 첫번째 노드를 삭제하지 않고 head_ptr을 바로 두번째 노드로 설정해도 되지만 이런방식은 첫번째 노드가 고립되 메모리를 차지하기 때문에 이런방식으로는 사용하지 않는다.

void list_head_remove(node*& head_ptr)
{
	node* remove_ptr;

	remove_ptr = head_ptr;
	head_ptr = remove_ptr->link();
	delete remove_ptr;
}

Remove

링크드 리스트에서 previous_ptr(특정 포인터)가 가리키는 노드 바로 다음 노드를 제거하는 함수다.

제거할 노드에 대한 remove_ptr이라는 임시 포인터를 설정해 시작한다.

1. remove_ptr을 설정

2. previous_ptr->set_link(remove_ptr->link());

3. delete remove_ptr; //노드의 메모리를 힙으로 리턴한다.

void list_remove(node* previous_ptr)
{
	node* remove_ptr;
	//제거하고자 하는 노드를 가르키는 remove_ptr
	remove_ptr = previous_ptr->link();
	//remove_ptr는 previous_ptr의 다음 노드다.
	previous_ptr->set_link(remove_ptr->link());
	//previous_ptr의 링크를 remove_ptr의 링크로 변환
	delete remove_ptr;
}

Clear

링크드 리스트에서 모든 노드를 제거해 빈 리스트로 만드는 함수다.

여기서 리스트의 모든 노드를 삭제하지 않고 head_ptr을 NULL로 만들면 전체 리스트가 손실된다. 따라서 목록이 비워질 때까지 list_head_remove 함수를 반복해서 사용해야 한다.

void list_clear(node*& head_ptr)
{
	while(head_ptr != NULL)
		list_head_remove(head_ptr);
}

Twitter Facebook LinkedIn