[자료구조] 연결 리스트

 

 

목차

 

 

---

 

연결 리스트

연결 리스트(=링크드 리스트 Linked List)는 노드를 연결해서 만든 리스트이다. 각각의 연결 리스트의 노드는 '데이터'와 '다음 노드에 대한 포인트'로 이루어진다.

 

---

연결리스트

 

 

#include <iostream>
#include <list>
using namespace std;
 
int main()
{
    list<int> li;
 
    list<int>::iterator eraseIt;
 
    // [ ] <-> [ ] <-> [ ]
    for (int i = 0; i < 10; i++)
    {
        if (i == 5)
        {
            eraseIt = li.insert(li.end(), i);  // li.end()위치 바로 앞에 데이터를 넣어준다.
        }
        else
        {
            li.push_back(i);
        }        
    }
 
    li.erase(eraseIt);
 
    for (list<int>::iterator it = li.begin(); it != li.end(); it++)
    {
        cout << (*it) << endl;
    }
}
 

- li.push_back(i) : 0, 1, 2, 3, 4, 6, 7, 8, 9 값을 할당한다

- 0, 1, 2, 3, 4 값이 들어가 있는 상태에서 li.insert(li.end(), i). 

- i = 5 일 때, eraseIt = li.insert(li.end(), 5) : 끝 위치에 5 삽입.

- eraseIt를 통해서 5를 지운다.

 

- Iterator를 사용하면 코드의 재사용성이 좋아진다.

 

 

 

전체코드

전체코드

#include <iostream>
#include <vector>
#include <list>
using namespace std;
 
template<typename T>
class Node
{
public:
    Node() : _prev(nullptr), _next(nullptr), _data(T())
    {
 
    }
 
    Node(const T& value) : _prev(nullptr), _next(nullptr), _data(value)
    {
 
    }
 
public:
    Node*    _prev;
    Node*    _next;
    T        _data;
};
 
template<typename T>
class Iterator
{
public:
    Iterator() : _node(nullptr)
    {
 
    }
 
    Iterator(Node<T>* node) : _node(node)
    {
 
    }
 
    // ++it
    Iterator& operator++()
    {
        _node = _node->_next;
        return *this;
    }
 
    // it++
    Iterator operator++(int)
    {
        Iterator<T> temp = *this;
        _node = _node->_next;
        return temp;
    }
 
    // --it
    Iterator& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
 
    // it--
    Iterator operator--(int)
    {
        Iterator<T> temp = *this;
        _node = _node->_prev;
        return temp;
    }
 
    // *it
    T& operator*()
    {
        return _node->_data;
    }
 
    bool operator==(const Iterator& other)
    {
        return _node == other._node;
    }
 
    bool operator!=(const Iterator& other)
    {
        return _node != other._node;
    }
 
public:
    Node<T>* _node;
};
 
template<typename T>
class List
{
public:
    List() : _size(0)
    {
        // [head] <-> ... <-> [tail]
        _head = new Node<T>();
        _tail = new Node<T>();
        _head->_next = _tail;
        _tail->_prev = _head;
    }
 
    ~List()
    {
        while (_size > 0)
            pop_back();
 
        delete _head;
        delete _tail;
    }
 
    void push_back(const T& value)  // [tail] 바로 이전 위치에 데이터를 밀어넣어준다.
    {
        AddNode(_tail, value);
    }
 
    void pop_back()                    // [tail] 바로 이전 데이터를 꺼내준다.
    {
        RemoveNode(_tail->_prev);
    }
 
private:
    // [newNode] 생성하기
    // [head] <-> [1] <-> [prevNode] <-> [before] <-> [tail]
    // [head] <-> [1] <-> [prevNode] <-> [newNode] <-> [before] <-> [tail]
    Node<T>* AddNode(Node<T>* before, const T& value)
    {
        Node<T>* newNode = new Node<T>(value);
        Node<T>* prevNode = before->_prev;
 
        prevNode->_next = newNode;
        newNode->_prev = prevNode;
 
        newNode->_next = before;
        before->_prev = newNode;
 
        _size++;
 
        return newNode;
    }
    // [node] 삭제하기
    // [head] <-> [prevNode] <-> [node] <-> [nextNode] <-> [tail]
    // [head] <-> [prevNode] <-> [nextNode] <-> [tail]
    Node<T>* RemoveNode(Node<T>* node)
    {
        Node<T>* prevNode = node->_prev;
        Node<T>* nextNode = node->_next;
 
        prevNode->_next = nextNode;
        nextNode->_prev = prevNode;
 
        delete node;
 
        _size--;
 
        return nextNode;
    }
 
    int size() { return _size; }
 
public:
    using iterator = Iterator<T>;
 
    iterator begin() { return iterator(_head->_next); }
    iterator end() { return iterator(_tail); }
 
    // it '앞에' 추가
    iterator insert(iterator it, const T& value)
    {
        Node<T>* node = AddNode(it._node, value);
        return iterator(node);
    }
 
    iterator erase(iterator it)
    {
        Node<T>* node = RemoveNode(it._node);
        return iterator(node);
    }
 
private:
    Node<T>*    _head;
    Node<T>*    _tail;
    int            _size;
};
 
int main()
{
    List<int> li;
 
    List<int>::iterator eraseIt;
    // [ ] <-> [ ] <-> [ ] <-> [ ]  <-> [ ]  <-> [ ]
    for (int i = 0; i < 10; i++)
    {
        if (i == 5)
        {
            eraseIt = li.insert(li.end(), i); // li.end()위치 바로 앞에 데이터를 넣어준다.
        }
        else
        {
            li.push_back(i);
        }
    }
 
    li.pop_back();
 
    li.erase(eraseIt);
 
    for (List<int>::iterator it = li.begin(); it != li.end(); it++)
    {
        cout << (*it) << endl;
    }
 
}
 

 

Iterator 사용하는 이유

 

• 코드 재사용성이 용이하다.
• 인터페이스 통일.

 

---

 

 

 

연결리스트 코드

 

LinkedList.h

 

#pragma once

typedef int DataType;

struct Node
{
	DataType Data;
	Node* NextNode;
};

Node* Create(DataType data);
void Destroy(Node* node);

void Push(Node** head, Node* node);
void Insert(Node* current, Node* node);
void InsertHead(Node** current, Node* head);

void Remove(Node** head, Node* remove);
Node* GetNode(Node* head, int index);

int GetNodeCount(Node* head);

 

 

LinkedList.cpp

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

Node * Create(DataType data)
{
	Node* node = new Node();

	node->Data = data;
	node->NextNode = NULL;

	return node;
}

void Destroy(Node * node)
{
	delete node;
	node = NULL;
}

void Push(Node ** head, Node * node)
{
	if ((*head) != NULL)
	{
		Node* tail = (*head);

		while (tail->NextNode != NULL)
			tail = tail->NextNode;

		tail->NextNode = node;
	}
	else
	{
		*head = new Node();
	}
}

void Insert(Node * current, Node * node)
{
	node->NextNode = current->NextNode;
	current->NextNode = node;
}

void InsertHead(Node ** current, Node * head)
{
	if (*current == NULL)
	{
		*current = head;
	}
	else
	{
		head->NextNode = *current;
		*current = head;
	}
}

void Remove(Node ** head, Node * remove)
{
	if (*head == remove)
	{
		*head = remove->NextNode;
	}
	else
	{
		Node* current = *head;
		while (current != NULL && current->NextNode != remove)
			current = current->NextNode;

		if (current != NULL)
			current->NextNode = remove->NextNode;
	}
}

Node * GetNode(Node * head, int index)
{
	Node* current = head;

	while (current != NULL && (--index >= 0))
		current = current->NextNode;

	return current;
}

int GetNodeCount(Node * head)
{
	int count = 0;
	Node* current = head;

	while (current != NULL)
	{
		current = current->NextNode;
		count++;
	}

	return count;
}

 

 

Execute.cpp

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

int main()
{
	Node* node = NULL;
	for (int i = 0; i < 5; i++)
	{
		Node* temp = Create(i);
		Push(&node, temp);
	}

	Node* newNode = NULL;
	{
		newNode = Create(-1);
		InsertHead(&node, newNode);

		newNode = Create(-2);
		InsertHead(&node, newNode);
	}

	//Print
	{
		Node* current = GetNode(node, 2);
		newNode = Create(1000);

		Insert(current, newNode);

		int count = GetNodeCount(node);
		for (int i = 0; i < count; i++)
		{
			Node* current = GetNode(node, i);
			cout << "List[" << i << "] : " << current->Data << endl;
		}
		cout << "-------------------------------------------------" << endl << endl;
	}

	//Remove
	{
		Node* remove = GetNode(node, 3);
		Remove(&node, remove);

		int count = GetNodeCount(node);
		for (int i = 0; i < count; i++)
		{
			Node* current = GetNode(node, i);
			cout << "List[" << i << "] : " << current->Data << endl;
		}
		cout << "-------------------------------------------------" << endl << endl;
	}

	//Remove All
	{
		int count = GetNodeCount(node);

		for (int i = 0; i < count; i++)
		{
			Node* current = GetNode(node, 0);

			if (current != NULL)
			{
				Remove(&node, current);
				Destroy(current);
			}
		}

		int a = 0;
	}
	
	return 0;
}

 

---