연결리스트

Linked list

Node(class)설계방식

data와 next(다음 Node를 가리키는 포인터)로 이루어져 있다.
생성자의 parameter를 잘 설정해야 한다.

#include <iostream>

using namespace std;

class Node {
	friend class LinkedList;
private:
	int	data;
	Node *next;
public:
	Node(int tmp, Node *n)
	{
		data = tmp;
		next = n;
	}
	Node()
	{
		data = 0;
		next = NULL;
	}
	
	//추가함수
	int getdt()
	{
		int p;
		p = data;
		return p;
	}
};

LinkedList(class) 설계방식

리스트의 head(Node), tail(Node) 그리고 List의 size로 이루어져 있다.
- insert함수와 delete함수가 존재 한다.
- List에 Node를 insert하는 방식이다.
원하는 index에 Node를 삽입 할 수 있다
1. idx = 0 –> head에 삽입 idx = size –> tail 의 삽입
  - 0 < idx < size –> 포인터(current)를 head에서 해당 index까지 이동 후 Node를 삽입
2. ’ List에서 Node를 delete하는 과정입니다.
  
  ‘원하는 index의 Node를 제거 할 수 있다.’
  - idx = 0 –> head를 다음노드(2번째노드)로 이동하고 head를 제거
  - idx != 0 –> 포인터(current)를 제거하려는 node전까지 이동
  - delNode를 current->next로 설정 후 delNode 삭제

class LinkedList {
private:
	Node	*head, *tail;
	int size;
public:
	LinkedList() {
		head = NULL;
		tail = NULL;
	}
	/*초기화 첫 value*/
	LinkedList(int data) {
		head = tail = new Node(data, NULL);
		size = 1;
	}
	
	void insert(int data, int idx)
	{
		Node *newNode = new Node(data, NULL);
		Node *current = head;
		if (idx > size || idx < 0)
		{
			cout << "index 초과" << endl;
		}
		else
		{
			if (idx == 0)  //head삽입
			{
				if (head == NULL)
					tail = newNode;
				else
					newNode->next = head;
				head = newNode;
			}
			else if (idx = size)   //tail삽입
			{
				if (head == NULL)
					head = newNode;
				else
					tail->next = newNode;
				tail = newNode;
			}
			else {
				int i = 0;
				//current 포지션 idx로 이동
				while (i < idx - 1)
				{
					current = current->next;
					i++;
				}
				newNode->next = current->next;
				current->next = newNode;
			}
		}
		size++;
	}
	
	void deletedata(int idx)
	{
		if (head != NULL)
		{
			Node* current = head;
			Node* delNode;
			int i = 0;
			
			if (idx == 0)
			{
				head = head->next;
				delete current;
			}
			else {  
				//제거하려는 노드의 이전노드까지이동
				while (i < idx - 1)
				{
					current = current->next;
					i++;
				}
				delNode = current->next;
				current->next = current->next->next;
				delete delNode;
			}
			size--;
		}
	}
	
	//추가함수
	int getData(int idx)
	{
		int i = 0;
		Node *current = head;
		while (i < idx)
		{
			current = current->next;
			i++;
		}
		return current->getdt();

	}
};

lst라는 Node insert과정을 거치면 1 -> 2 -> 3 -> 4 -> 5 가 됩니다.

lst->deletedata(2) 는 index=2인 Node를 삭제합니다.

그러므로 3이 삭제되어 1 -> 2 -> 4 -> 5 가 됩니다.

int main(void)
{
	LinkedList* lst = new LinkedList(1);
	lst->insert(2, 1);
	lst->insert(3, 2);
	lst->insert(4, 3);
	lst->insert(5, 4);
	
	//확인
	cout << lst->getData(0) << lst->getData(1) << lst->getData(2) << lst->getData(3) << lst->getData(4)<<endl;

	lst->deletedata(2);
	cout << lst->getData(0) << lst->getData(1) << lst->getData(2) << lst->getData(3);
	return 0;
}