자료구조 - Linked List

Linked List는 노드 들간의 연결된 포인터들로 구성되는 자료구조이다. 배열과 같이 원소가 선형으로 저장된다는 특성이 있지만 배열과는 달리 중간에 원소의 삽입 삭제가 가능하고 중간에 있는 원소에 접근하기 위해서는 Head에서부터 순차적으로 접근해서 찾는 방식을 취할 수 밖에 없다.

배열과 Linked List는 다음과 같은 차이점을 가지고 있다.

• Linked List
  • 원소에 대한 접근을 Head부터 다음 노드로 순차적으로 찾아가야 하기 때문에 검색시간은 O(n)이다.
  • 원소를 중간에 삽입, 삭제하는 것이 매우쉽다 ( 전 후 노드가 가르키는 포인터를 바꾸어 주면 된다. )
  • List로 연결된 요소들이 메모리상에 연속적으로 저장되지 않아도 된다.
• 배열
  • 메모리상에 연속적으로 저장된 공간이므로 첫주소만 알면 상대적인 주소를 계산해 상수시간 O(1)으로 원소에 접근이 가능하다.
  • 원소를 중간에 삽입,삭제하는 것이 어렵다. 연속된 저장공간이기 때문에 배열의 할당크기를 늘려주어야 하고 삽입하는 지점부터의 원소들을 다시 복사해 주어야 한다.
  • 배열은 메모리상에 연속적으로 저장되어 있다.

#include <cstdio>
#include <stdlib.h>
#define INF -987654321

using namespace std;


typedef struct Node
{
	Node* prev;
	Node* next;
	int value;

	Node(int v)
	{
		value = v;
	}
}node;

class LinkedList
{
private:
	Node* head;
	Node* tail;
	int size = 0;
public:

	LinkedList()
	{

	}
	int getSize()
	{
		return size;
	}

	void pushFront(int value)
	{
		Node* target = (Node*)malloc(sizeof(Node));
		target->prev = NULL;
		target->next = NULL;
		target->value = value;

		if (head == NULL)
		{
			head = target;
			tail = target;
		}
		else
		{
			head->prev = target;
			target->next = head;
			head = target;
		}
		size++;
	}

	void pushBack(int value)
	{
		Node* target = (Node*)malloc(sizeof(Node));
		target->value = value;

		target->prev = NULL;
		target->next = NULL;

		if (tail == NULL)
		{
			head = target;
			tail = target;
		}
		else
		{
			tail->next = target;
			target->prev = tail;
			tail = target;
		}
		size++;
	}

	void insertAt(int index, int value)
	{
		Node* offset = head;
		bool exist = true;
		while (index--)
		{
			if (offset->next != NULL)
				offset = offset->next;
			else
				exist = false;
		}

		if (exist)
		{
			Node* target = (Node*)malloc(sizeof(Node));
			
			target->prev = offset->prev;
			target->next = offset;
			target->value = value;

			if (offset->prev->next != NULL)
				offset->prev->next = target;
			offset->prev = target;

			size++;
		}
		else
		{
			printf("That Node Not Exist!\n");
		}
	}

	int popFront()
	{
		if (head == NULL)
		{
			return INF;
		}
		else
		{
			size--;
			int value = head->value;
			head = head->next;
			return value;
		}
	}

	int popBack()
	{
		if (tail == NULL)
		{
			return INF;
		}
		else
		{
			size--;
			int value = tail->value;
			tail = tail->prev;

			return value;
		}
	}

	

};

void main()
{
	LinkedList l1;

	for (int i = 0; i < 10; i++)
		l1.pushBack(i);

	while (l1.getSize() != 0)
	{
		if (l1.getSize() % 2 == 0)
			printf("%d ", l1.popBack());
		else
			printf("%d ", l1.popFront());
	}

}