[자료구조] C++로 쉽게 풀어쓴 자료구조 : 6장, List

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

1) 6장. 리스트

앞에서 배운 스택, 큐, 덱과 같이 리스트 또한 선형 자료구조 이다. 선형이란 원소들이 일렬로 순서대로 들어있는것을 말한다. list와 이들 자료구조의 차이는 무엇일까? 답은 원소에 대한 접근 방법이 다르다는 것 이다. 스택이나, 큐, 덱같은 경우 자료의 접근은 front나 rear을 통해서만 접근이 가능하다. 중간에 원소를 삽입하는것을 허용하지 않는다. list는 이러한 제한이 없다. 임의접근이 가능한것이다.

 

List의 ADT

데이터: 임의 접근 방법을 제공하는 타입이 같은 요소들의 순서있는 모임.

 

연산:

- insert(pos, item): list의 pos위치에 새로운 요소 item 삽입한다.

- delete(pos): list의 pos 위치의 요소를 삭제.

- getEntry(pos): list의 pos 위치의 요소를 반환.

- isEmpty(): list가 비어있는지 검사.

- isFull(): list가 가득 차 있는지 검사.

- find(item): list에 item이 있는지 확인.

- replace(pos, item): list의 pos위치에 있는 요소를 새로운 item으로 바꾼다.

- size(): list안의 요소의 개수를 반환

- display(): list안의 모든 요소들을 출력한다.

 

크게 배열로 구현한 리스트와 연결리스트로 구현한 리스트 2가지의 주제에 관하여 배우는 시간이였다.

 

 

단순 연결 리스트

연결 리스트로 구현된 list의 다이어그램

C++같은 객체지향 프로그래밍에서는 작은 class에서 할수있는 가능한 많은 기능을 구현하는 것 이다. 한 Node에서 다음 노드를 삭제하거나 , 자신의 다음에 어떤 Node를 삽입하는 작업은 전체 List 의 정보가 없어도 처리할 수 있다. 따라서 이들은 Node class의 멤버 함수로 구현해주는 것 이 좋다.

 

getEntry() 에 대해서 먼저 확인해보자. 이 함수는 pos번째 node의 주소값을 반환한다.

Node* getEntry(const int& pos)
{
	Node* temp = &_org;
	for (int i = -1; i < pos; i++) { // -1부터 시작
		if (temp == nullptr) break;
		temp = temp->getLink();
	}
	return temp;
}

 

pos값이 0 getEntry(0)과 getHead()는 동일한 값을 반환한다. 또한 getEntry(-1)는 nullptr이 아니라 헤드 노드의 주소를 반환하도록 설계되어있다.

 

내가 궁금한건 왜 -1이 꼭 헤드노드의 주소를 반환해야하는가?? 이였다.

 

이는 다음 함수인 insert()를 보게된후 알게되었다.

 

insert() 에서는 pos값이 0인경우 getEntry()의 인자로 -1이 전달되는데, 이때 헤드노드를 가리키도록 사용되는 것 이였다.

void LinkedList::insert(const int& pos, Node* n)
{
	Node* prev = getEntry(pos - 1);
	if (prev != nullptr)
		prev->insertNext(n);
}

 

즉 pos가 0인 Node에 삽입을 하건, 삭제를 하건 이를 위해서 -1부터 사용하는 것 이였다. 이제 왜 헤드노드의 주소를 반환해야하는지는 알겠다.

 

하지만 두번째 의문이 들었다. i가 0부터 시작해도 getEntry(-1)은 for문의 조건식을 만족하지 못하기 때문에( 0 < -1 ) 똑같이 헤드노드의 주소를 반환한다. 그렇다면 왜 0이 아니라 -1부터 index를 사용하는 것 일까?

 

이에 의문이 들어 디버깅을 해본결과 의문을 해결할 수 있었다.

 

예를 들어 insert(1, new Node(30))을 수행한다 해보자. 그럼 insert함수에 pos값 1이 전달되고, 이는 다시 getEntry에는 0으로 전달된다. 이제 getEntry 함수 내부에서가 중요하다.

 

- i 가 0 부터인 경우: pos가 0 이니 0 < 0은 거짓이 되어 for문 안의 연산이 진행되지 않았고, 따라서 head 노드를 가리키게 된다.

- i 가 -1 부터인 경우: pos가 -1 이니 -1 < 0은 참이 되어 for문 안의 연산이 한번 진행되었고, 따라서 0번 노드를 가리키게 된다.

Node.h

#pragma once
#include <iostream>

inline void error(const char* message) {
	printf("%s\n", message);
	exit(1);
}

class Node {
	Node* _link;
	int _data;
public:
	Node(int value = 0) : _data(value), _link(nullptr) {}
	Node* getLink() { return _link; }
	void setLink(Node* next) { _link = next; }
	void display() { std::cout << '[' << _data << "] "; }
	bool hasData(const int& value) { return _data == value; }
	void insertNext(Node* n);
	Node* removeNext();
	int getData() { return _data; }
};

void Node::insertNext(Node* n)
{
	if (n != nullptr){
		n->_link = _link;
		_link = n;
	}
}

Node* Node::removeNext()
{
	Node* removed = _link;
	if(removed != nullptr)
		_link = removed->_link;
	return removed;
}

 

LinkedList.h

#pragma once
#include "Node.h"

class LinkedList {
	Node _org;
public:
	LinkedList() : _org(0) {}
	~LinkedList() { clear(); }
	void clear() { while (!isEmpty()) delete remove(0); }
	Node* getHead() { return _org.getLink(); }
	bool isEmpty() { return getHead() == nullptr; }

	Node* getEntry(const int& pos);
	void insert(const int& pos, Node* n);
	Node* remove(const int& pos);
	Node* find(const int& value);
	void replace(const int& pos, Node* n);
	int size();
	void display();
};

Node* LinkedList::getEntry(const int& pos)
{
	Node* temp = &_org;
	for (int i = -1; i < pos; i++) { // -1부터 시작
		if (temp == nullptr) break;
		temp = temp->getLink();
	}
	return temp;
}

void LinkedList::insert(const int& pos, Node* n)
{
	Node* prev = getEntry(pos - 1);
	if (prev != nullptr)
		prev->insertNext(n);
}

Node* LinkedList::remove(const int& pos)
{
	Node* prev = getEntry(pos - 1);
	return prev->removeNext();
}

Node* LinkedList::find(const int& value)
{
	for (Node* p = getHead(); p != nullptr; p = p->getLink())
		if (p->hasData(value)) return p;
	return nullptr;
}

void LinkedList::replace(const int& pos, Node* n)
{
	Node* prev = getEntry(pos - 1);
	if (prev != nullptr) {
		delete prev->removeNext();
		prev->insertNext(n);
	}
}

int LinkedList::size()
{
	int count = 0;
	for (Node* start = getHead(); start != nullptr; start = start->getLink())
		count++;
	return count;
}

void LinkedList::display()
{
	std::cout << "[전체 항목 수 = " << size() << "] : ";
	for (Node* start = getHead(); start != nullptr; start = start->getLink())
		start->Node::display();
	std::cout << std::endl;
}

 

main.cpp

#include <iostream>
#include <cstdio>
#include "LinkedList.h"
using namespace std;

int main(){
	LinkedList list;
	list.insert(0, new Node(10));
	list.insert(0, new Node(20));
	list.display();
	list.insert(1, new Node(30));
	list.display();
	list.insert(list.size(), new Node(40));
	list.display();
	list.insert(2, new Node(50));
	list.display();

	Node* temp = list.getEntry(-1);
	cout << (*temp).getData() << endl;

	list.remove(2);
	list.remove(list.size() - 1);
	list.remove(0);
	list.replace(1, new Node(90));
	list.display();

	list.clear();
	list.display();

	return 0;
}

 

결과로는 다음과 같다.

 

이중 연결 리스트

간단하게 코드만

 

Node2.h

#pragma once
#include <iostream>

class Node2 {
	Node2* _prev;
	Node2* _next;
	int _data;
public:
	Node2(int value = 0) : _data(value), _prev(nullptr), _next(nullptr) {}
	Node2* getPrev() { return _prev; }
	Node2* getNext() { return _next; }
	void setPrev(Node2* p) { _prev = p; }
	void setNext(Node2* p) { _next = p; }
	void display() { std::cout << '[' << _data << "] "; }
	bool hasData(const int& value) { return _data == value; }
	void insertNext(Node2* n);
	Node2* remove();
};

void Node2::insertNext(Node2* n)
{
	if (n != nullptr) {
		n->_prev = this;
		n->_next = this->_next;
		if(_next != nullptr)
			this->_next->_prev = n;
		this->_next = n;
	}
}

Node2* Node2::remove()
{
	if (_prev != nullptr) _prev->_next = _next;
	if (_next != nullptr) _next->_prev = _prev;
	return this;
}

 

 

DLinkedList.h

#pragma once
#include "Node2.h"

class DLinkedList {
	Node2 _org;
public:
	DLinkedList() : _org(0) {}
	~DLinkedList() { clear(); }
	void clear() { while (!isEmpty()) delete remove(0); }
	Node2* getHead() { return _org.getNext(); }
	bool isEmpty() { return getHead() == nullptr; }

	Node2* getEntry(const int& pos);
	void insert(const int& pos, Node2* n);
	Node2* remove(const int& pos);
	Node2* find(const int& value);
	void replace(const int& pos, Node2* n);
	int size();
	void display();
};

Node2* DLinkedList::getEntry(const int& pos)
{
	Node2* temp = &_org;
	for (int i = -1; i < pos; i++) { // -1부터 시작
		if (temp == nullptr) break;
		temp = temp->getNext();
	}
	return temp;
}

void DLinkedList::insert(const int& pos, Node2* n)
{
	Node2* prev = getEntry(pos - 1);
	if (prev != nullptr)
		prev->insertNext(n);
}

Node2* DLinkedList::remove(const int& pos)
{
	Node2* n = getEntry(pos);
	return n->remove();
}

Node2* DLinkedList::find(const int& value)
{
	for (Node2* p = getHead(); p != nullptr; p = p->getNext())
		if (p->hasData(value)) return p;
	return nullptr;
}

void DLinkedList::replace(const int& pos, Node2* n)
{
	Node2* prev = getEntry(pos - 1);
	if (prev != nullptr) {
		delete prev->getNext()->remove();
		prev->insertNext(n);
	}
}

int DLinkedList::size()
{
	int count = 0;
	for (Node2* start = getHead(); start != nullptr; start = start->getNext())
		count++;
	return count;
}

void DLinkedList::display()
{
	std::cout << "[전체 항목 수 = " << size() << "] : ";
	for (Node2* start = getHead(); start != nullptr; start = start->getNext())
		start->Node2::display();
	std::cout << std::endl;
}

 

이를 활용하여 덱 또한 연결리스트로 구현할 수 있다. 구현된 멤버함수들을 재사용 하면 된다. 상속의 강력함 또한 느낄수 있다.

class LinkedDeque : public DLinkedList {
public:
	void addFront(Node2* n) { insert(0, n); }
	Node2* deleteFront() { return remove(0); }
	Node2* getFront() { return getEntry(0); }
	void addRear(Node2* n) { insert(size(), n); }
	Node2* deleteRear() { return remove(size()-1); }
	Node2* getRear() { return getEntry(size()-1); }
};

 

---

2) 나의 현황

◆ 방학이 끝나가는구나.. 뭐 휴학예정이라 나랑은 상관없겠지만..

 

책에서 간단히 말로만 설명하고 넘어간 원형연결리스트는 GeeksforGeeks에서 보충하였다.

Circular Linked List | Set 2 (Traversal) - GeeksforGeeks

 

​이글의 모든 사진과 내용의 출처는 천인국, 최영규 님께 있습니다.