연결형 리스트 (1)

Yama·2023년 12월 19일

C/C++어소트락 취업반

어소트락 수업

목록 보기

18/55

동적 배열(가변 배열)

더 큰 배열을 넣고 싶을떄 공간을 확장해서 새로운 공간에 옮겨서 주소를 바꿔서 저장했다.

연결형 리스트

데이터 하나 들어가면 하나의 공간을 할당하고 넣은 순서대로 주소를 알고 있다.
리스트 본체는 첫번째 주소만 알면 모든 데이터 값을 알 수 있다.
다음 데이터의 주소를 연결을해서 접근 가능하게 하는 컨테이너를 연결형 리스트라 한다.

참고 : 면접에서는 무슨 장점이 있냐 어케 쓰냐 이런거 대답할수 있게 공부해라.

동적 배열과 연결형 리스트 장단점.

동적 배열 장점
- 데이터 접근을 인덱싱으로 접근 할 수 있다.
  - 첫번째 주소를 알면 +99인덱싱하면 100번쨰 주소를 바로 알수 있다.
  - O(1).
동적 배열 단점
- 불필요한 데이터를 삭제하거나 지정된 위치에 데이터를 삽입할때 비효율(문제)이 발생한다.
  - 중간에 값을 삭제하면 그 뒤의 값들을 한칸씩 떙겨와야된다.
  - 중간에 값을 넣을때는 그 뒤의 값들을 한칸씩 밀어줘야한다.
  - O(n)
연결형 리스트 장점
- 데이터를 중간에 데이터를 삭제하거나 새로운 데이터가 들어와도 비효율적이지 않다.
  - 시작점을 잃어도 다음 데이터를 시작점으로 지목한다.
  - 중간을 잃은 경우 1->2->3 에서 2를 삭제하면 1->3으로 연결된다.
  - O(1)
연결형 리스트 단점
- n번쨰 데이터(원하는 데이터에)에 접근할떄는 느리다.
  - 연결이 되어있어서 그 값을 찾을려면 전값을 알아야되서.
  - O(n)

연결형 리스트 구현하기 - 구조체 만들기(관리자 개체)

LinkedList.h

struct Node
{
	int Data; // 4
    Node* pNext; // 5
}

struct LinkedList
{
	Node* 		pHeadNode; // 1
	int			CurCount; // 2
	// int		MaxCount; // 3
};

void PushBack(LinkedList* _List, int _Data); // 6

// 1 은 힙메모리 활용할려고 포인터 변수를 사용한다.
// 2 는 현재값.
// 3은 연결형 리스트에서 필요가없다.
- 가변 배열에서는 메모리를 연속적으로 관리하기 떄문이다.
- 반면에 연결형 리스트는 연속적이지 않고 곳곳에 흝어진것이 연결된건라 데이터 최대값을 관리해줄 필요 없다.
// 4는 그 노드에 저장할 데이터를 관리한다.
// 5는 주소값을 관리하는 노드다.
// 6은 연결형 데이터 추가 함수일것이다.?

연결형 리스트 구현하기 - 실제 구현.

LinkedList.cpp

#include <iostream>

#include "LinkedList.h"

// 13
void PushBack(LinkedList* _List, int _Data)
{
	if (nullptr == _List->pHeadNode)
	{
		Node* pNewNode = (Node*)malloc(sizeof(Node)); 
		pNewNode->Data = _Data;
		pNewNode->pNext = nullptr;

		_List->pHeadNode = pNewNode;
		_List->CurCount++;
	}
	else
	{
		Node* pNewNode = (Node*)malloc(sizeof(Node));
		pNewNode->Data = _Data;
		pNewNode->pNext = nullptr;

		Node* pNode = _List->pHeadNode;

		while (true)
		{
			pNode =	pNode->pNext;
			if (nullptr == pNode->pNext)
			{
				break;
			}
		}

		//while (pNode->pNext == nullptr)
		//{
		//	pNode = pNode->pNext;
		//}

		pNode->pNext = pNewNode;

		_List->CurCount++;

	}
	_List->CurCount++;
}

만약 입력되는 데이터가 처음일 경우.
- if문에는 HeadNode값이 0이면 실행이 되게 설계한다.
```
	if (nullptr == _List->pHeadNode)
```
- 입력된 데이터를 저장할 새로운 노드를 할당받는법.
- 노드 포인터는 노드로 받는다(같은 포인터끼리끼리)
- 데이터를 저장할 노드 생성, 데이터 복사
```
			Node* pNewNode = (Node*)malloc(sizeof(Node)); 
			pNewNode->Data = _Data;
			pNewNode->pNext = nullptr;
```
- 처음 만든 노드에 주소값을 헤더에 넣어준다.
```
	_List->pHeadNode = pNewNode;
```
- 데이터 카운트를 1 증가 시킨다.
```
	_List->CurCount++;
```

리스트에 입력된 데이터가 1개 이상이라면

입력된 데이터를 저장할 새로운 노드를 할당받는법.

			Node* pNewNode = (Node*)malloc(sizeof(Node)); 
			pNewNode->Data = _Data;
			pNewNode->pNext = nullptr;

리스트가 보유한 노드 중, 가장 마지막 노드를 찾는다.(다음이 널이면 현재 마지막)

		Node* pNode = _List->pHeadNode;

		while (true) // 1
		{
			pNode =	pNode->pNext;
			if (nullptr == pNode->pNext)
			{
				break;
			}
		}
  
  		while (pNode->pNext == nullptr) // 1의 축약 버전.
		{
			pNode = pNode->pNext;
		}

찾은 노드의 pNext를 현재 생성된 노드를 가리킨다(연결).

		pNode->pNext = pNewNode;

데이터 카운트를 1 증가 시킨다.

	_List->CurCount++;

중복 제거.

위로 올려서 중복 코드 제거.

  		Node* pNewNode = (Node*)malloc(sizeof(Node)); 
		pNewNode->Data = _Data;
		pNewNode->pNext = nullptr;

if, else문 밖으로 뺴서 하자.

  	_List->CurCount++;

줄이기

	while (true) // 1
	{
		pNode = pNode->pNext;
	
		if (nullptr == pNode->pNext)
     	{
			break;
		}
    }

	while (pNode->pNext) { pNode = pNode->pNext; } // 2

// 2번은 1번의 축약버전 이유:
- nullptr == pNode->pNext이면 break;인데 널은 어차피 0니까 폴스다. 근데 이게 널이 아닌동안 반복문 돌면된다는 이유로 축약했다.

단축키

일괄 선언 바꾸기: Ctrl + r + r

강의 코드

main.cpp

#include <iostream>

#include "LinkedList.h"

int main()
{
	LinkedList mylist = {};

	PushBack(&mylist, 10);
	PushBack(&mylist, 10);
	PushBack(&mylist, 10);

	return 0;
}

LinkedList.h

#pragma once

struct Node
{
	int		Data;
	Node* pNext;
};

struct LinkedList
{
	Node* pHeadNode;
	int		CurCount;
};

void PushBack(LinkedList* _List, int _Data);

LinkedList.cpp

#include "LinkedList.h"

#include <iostream>

void PushBack(LinkedList* _List, int _Data)
{
	Node* pNewNode = (Node*)malloc(sizeof(Node));
	pNewNode->Data = _Data;
	pNewNode->pNext = nullptr;

	if (nullptr == _List->pHeadNode)
	{
		_List->pHeadNode = pNewNode;
	}

	else
	{
		Node* pNode = _List->pHeadNode;

		/*while (true)
		{
			pNode = pNode->pNext;

			if (nullptr == pNode->pNext)
				break;
		}*/

		while (pNode->pNext) { pNode = pNode->pNext; }

		pNode->pNext = pNewNode;
	}

	_List->CurCount++;
}