3장-3. 단일 링크드 리스트 (String 버전)

단일 링크드 리스트란?

• 링크드 리스트 중에서 가장 단순한 형태
• 단일 노드들로 연결된 노드들이 연결된 집합
• 각각의 노드는 다음 노드를 가리키는 포인터 next를 저장하고
• 그와 관계된 원소를 저장한다.
• 링크드 리스트의 제일 처음과 마지막 요소를 head와 tail이라고 한다.

 

#pragma once
class StringNode
{
	string elem;
	StringNode* next;

	friend class StringLinkedList;
};

• StringNode.h

 

#pragma once
class StringLinkedList
{
public:
	StringLinkedList();
	~StringLinkedList();

	bool empty() const;
	const string& front() const;
	void addFront(const string& e);
	void removeFront();


private:
	StringNode* head;
};

• StringLinkedList.h

 

 

#include "pch.h"
#include "StringLinkedList.h"
#include "StringNode.h"

StringLinkedList::StringLinkedList()
	: head(nullptr)
{}

StringLinkedList::~StringLinkedList()
{
	while (!empty())
		removeFront();
}

bool StringLinkedList::empty() const
{
	return (head == nullptr);
}

const string& StringLinkedList::front() const
{
	return head->elem;
}

• StringLinkedList.cpp

 

 

 

 

---

링크드 리스트 앞에 삽입

 

void StringLinkedList::addFront(const string& e)
{
	StringNode* v = new StringNode; // 노드 생성
	v->elem = e;			// 입력 받은 값을 새 노드의 값으로 설정
	v->next = head;			// 이 노드는 헤드를 가리킴
	head = v;			// 이제 이 노드가 head가 됨
}

 

 

 

 

 

 

 

---

링크드 리스트 앞에서 삭제

 

void StringLinkedList::removeFront()
{
	StringNode* old = head; // 헤드를 가져온다.
	head = old->next;	// 헤드를 기존 헤드의 다음 요소로 재설정
	delete old;		// 헤드 삭제
}

• 삭제하기 위해선 head가 바로 이전 노드를 가리키도록 해야 한다.