List, 연결List, 단순연결List

1. List

 🍀 순서를 가진 데이터의 집합을 가리키는 추상 자료형

    ✏️ 동일한 데이터를 가지고 있어도 상관 없음.

    ✏️ 구현 방법에 따라 크게 두 가지로 나뉨.

      ▪ 순차 List : 배열을 기반으로 구현된 List

      ▪ 연결 List : 메모리의 동적할당을 기반으로 구현된 List

    ✏️ 주요 함수

      ▪ addtoFirst()

      ▪ addtoLast()

      ▪ add()

      ▪ delete()

      ▪ get() : 특정 위치 원소를 return

 

 

2. 연결 List

 🍀 단순 배열을 이용한 순차 List의 단점을 보완한 자료구조

    ✏️ 개별적으로 위치하고있는 원소의 주소를 연결하여 하나의 전체적인 자료구조를 이룸

    ✏️ 순차 List에서 물리적인 순서를 맞추기 위한 작업이 필요하지 않음.

    ✏️ 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능.

    ✏️ 단점 : 구현이 배열 List보다 복잡함.

      📌 노드 : 연결 List에서 하나의 우너소에 필요한 data를 갖고 있는 자료의 단위.

        ▪ 데이터 필드 : 원소의 값을 저장하는 자료구조. 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용

        ▪ 링크 필드 : 다음 노드의 주소를 저장하는 자료구조

      📌 헤드 : List의 처음 노드를 가리키는 자료구조

 

 

3. 단순 연결 List

 🍀 처음 위치에 node를 삽입하기

addtoFirst(L, i)
	new <- createNode();
	new.data = i;
	new.link = L;
  	L = new;
end addtoFirst()

 

 🍀 임의의 위치에 node를 삽입하기

add(L, pre, i)
	new <- createNode()
	new.data = i;
	if (L=NULL) then {
		L = new;
		new.link = NULL;
	}
	else {
		new.link = pre.link;
		pre.link = new;
	}
end add()

 

 🍀 마지막 위치에 node를 삽입하기

addtoLast(L, i)
	new <- createNode()
	new.data = i;
	new.link = NULL;
	if (L=NULL) then {
		L = new;
		return;
	}
	temp = L;
	while (temp.link != NULL) do
		temp = temp.link;
	temp.link = new;
end.addtoLast()

 

 🍀 노드 삭제 알고리즘

delete(L, pre)
	if (L==NULL) then error;
	else {
		target = pre.link;
		if (target == NULL) then return;
		pre.link = target.link;
	}
	freeNode(target)
end delete()

 

 ✔ c++ 코드 구현 ✔

#define MAX_NODE 10000

struct Node {
	int data;
	Node* next;
};

Node node[MAX_NODE];
int nodeCnt = 0;
Node* head;

Node* getNode(int data) {
	node[nodeCnt].data = data;
	node[nodeCnt].next = nullptr;
	return &node[nodeCnt++];
}

void init() // 초기화
{
	head = getNode(-1);
	//nodeCnt = 0;
}

void addNode2Head(int data) // 앞에 넣기
{
	Node *newone;

    newone = getNode(data);
	newone->next = head->next;
	head->next = newone;
}

void addNode2Tail(int data) // 마지막에 넣기
{
	Node* ptr = head;
	while (ptr->next)
	{
		ptr = ptr->next;
	}
	ptr->next = getNode(data);
}

void addNode2Num(int data, int num) // 원하는 위치에 넣기
{
	int n = 1;
	Node* ptr = head;
	Node* curr;
	while (n < num)
	{
		if ((ptr->next) == nullptr)
			ptr->next = getNode(0);
		ptr = ptr->next;
		n++;
	}
	curr = ptr->next;
	ptr->next = getNode(data);
	ptr = ptr->next;
	ptr->next = curr;
}

void removeNode(int data) // 삭제
{
	Node* ptr = head;
	Node* curr;
    
	while (ptr->next)
	{
        if (ptr->next->data == data)
        {
            curr = ptr->next;
        	ptr->next = curr->next;
            break;
        }
		ptr = ptr->next;
	}
}


int getList(int output[MAX_NODE]) // 원하는 Node찾기
{
	Node* ptr = head->next;
	int cnt = 0;
	while (ptr)
	{
		output[cnt] = ptr->data;
		cnt++;
		ptr = ptr->next;
	}
	return (cnt);
}