[C++ 때려잡기] C++ 기초강의 5 링크드 리스트와 자료구조

2018/08/23 - [교육 노트/C++ 기초강의] - C++ 기초 강의 OT

이전에 동적할당을 배웠다

학생 관리 프로그램을 짠다고 했을때

이미 정해진 숫자의 회원을 관리할 때
User user_arr[10];
회원의 수가 프로그램 실행 도중에 정해질 때
User* user_arr = new User[number];

까지는 알고있을것이다.

그러나

회원의 수가 프로그램 실행 도중 계속 추가될 때, 얼만큼 들어올지 알지도 못할때
이럴때는 어떻게 해야할까?

그냥 사이즈를 엄청나게 크게 잡아놓고 있어야할까?

또 동적할당 하면 되는건가?

기존의 배열을

30명의 유저에서 31명으로 늘어나면
31명 배열을 만들고 기존의 30명을 복사한 뒤 1명을 추가한다.

-> 수가 늘어날 때마다 다시 배열을 할당하고
복사를 수행하고
….
-> 비 효율적!

굉장히 비효울적이다.

그래서 나온것이 링크드 리스트이다

1. 링크드 리스트 (linked list)

링크드 리스트는 선형 자료구조로

데이터 마다 다음 데이터를 가르키는 포인터를 연결하여 데이터를 연결한 구조이다.

여기서 하나의 자료를 담고있는것을 노드라고 한다.

위의 링크드 리스트의  노드를 구현해보면

과 같다.

링크드 리스트의 장단점을 살펴보면

링크드 리스트를 이용하면 학생이 추가되면 노드를 하나 더 만들고  마지막에 연결만 시켜주면 된다.

하지만 링크드 리스트의 경우 기본적으로 정보 하나를 저장할때 포인터를 추가로 저장해야하며

10번째 노드에 접근하고 싶으면 처음 노드 부터 포인터를 타고 10번째 까지 가야한다.

또한 한번 뒤로 가면 앞을 가르키는 포인터가 없어 앞의 원소에 접근하려면 다시 처음 노드부터 포인터를 타고 가야한다.

그래서 앞에 노드를 가르키는 포인터까지 추가한것이 더블 링크드 리스트이다

대신 링크드 리스트는 정보 하나를 저장할때 포인터 1개를  추가로 또 저장해야한다.

2. 자료구조

위에 링크드 리스트 설명에서 링크드 리스트가 선형 자료 구조라고 했다

여기서 자료구조는 무엇일까?

동적인 데이터 구성이나
특정한 상황에 최적화하여 데이터를
관리하기 위하여
데이터를 구조화하여 관리한다.
이를 자료구조 (Data-Structure)라 한다

다양한 자료 구조가 있는데

그중 간단한 자료구조가 스택과 큐이다.

스택은 쌓아올린 더미인데 자료가 들어올때 (push) 위로 쌓이고 자료가 나갈때 (pop)는 맨 위 (top) 이 나가는 형식이다

큐는 화장실 줄서기 와 비슷하다 먼저 들어온(enqueue) 아이템이 먼저 나가는(deaueue) 형식이다

그냥 오히려 자유롭게 쓸수있는 링크드리스트와 배열을 냅두고 왜 규약을 걸어놓은 이러한 자료구조가 왜 필요하느냐하면

게임을 하면 게임 대기열이 있을것이다.

그러면 게임을 하고자하는 유저를 순서대로 큐에 넣고  큐에서 빼면서 게임을 시켜주면된다.

이렇게 일정한 시스템에 맞는 자료구조가 존재하고 해당 자료구조를 적제 적소에 쓰면 더 많은 기능을 쓸필요도 없고

생각할 필요도 없다. 알아서 관리 되는것이다.

실습

1,링크드 리스트 구현

2. 스택을 일반 배열과 링크드 리스트로  구현 (push, pop, top, isfull, isempty)

3. 큐를 일반 배열과 링크드 리스트로 구현 (enqueue, dequeue, front, back, isFull, isEmpty)

이것으로 C++ 기초강의가 끝이며

다음 강의부터는 C++ 의 핵심인 클래스로 넘어가도록 하겠다.