[게임 프로그래머 입문 올인원] 선형 자료구조 1 : 연결 리스트 (47강)

B. 선형 자료구조

1. 연결 리스트

a.  노드

🌟 리스트를 구현할 때 가장 핵심

 

마트료시카...!  (노드라는 타입이 있다는 주장을 하는중)

 

46강에서 설명한 것 처럼, 101호 방 자체(데이터 공간)를 노드로 표현한다

 

b. 노드로 연결리스트 생성 (단방향)

노드 폼 완성

 

각 방을 생성해주고 이제 서로 연결해주면 됨

 

연결완성! (단방향 리스트)

 

void 말고 node로 바꿔주자

 

c. 단방향 리스트의 문제점

첫 번째 노드를 '헤드'라고 부르는데 (마지막 노드는 '테일')

 

마지막 값을 얻고 싶다면, 첫번째 부터 다 거쳐야 하고

중간에 값을 삽입하고 싶다면 그 전 후 값을 다 알아서 낑겨넣어줘야 함

 

👉 따라서 양방향으로 생성하는게 일반적임

 

d. 양방향 리스트 생성

전 노드 포인터 생성하고

 

양방향으로 만들어주면 됨

 

헤드와 테일을 아래와 같이 따로 지정해줘야함

 

4는 강의 오타난거 수정

 

 

2. 실습 : 미로 맵 만들어보기

a. Maze 프로젝트 생성

이런 형식으로 만들어주고 (소스파일을 Main으로 이름변경)

 

b. 기본적인 틀 생성하기

노드 기초 틀 생성

 

리스트에서는 노드를 헤드부분으로 넣어 줄 예정

 

이런식으로

 

c. 노드 생성하기

1) 첫 노드 추가

첫 노드 생성하기

 

 

2) 첫 노드가 아닌 노드 추가

 

노드 앞쪽에 추가하기

 

리스트 전체 코드

 

d. dummy node

첫 노드를 추가할 때 예외처리 해줘야 하는 번거로움 때문에

의미없는 dummy node를 추가해서 처리하는 경우가 있음

 

더미 두개를 양방향으로 먼저 생성함

 

생성자 부분에 의미없는 노드 두개 생성해준다

 

e. node 삭제하기

결국 데이터도 마지막엔 소멸자에서 소멸해줘야 함

 

 

f. dummy node를 활용한 AddAtHead 수정하기

더미사이에 노드를 넣어야 함

 

노드끼리의 연결관계를 생성해준다

 

g. AddAtTail 생성하기 

위에서 생성한 AddAtHead와 반대로 생성하면 됨

 

AddAtHead와 반대로 생성하면 됨

 

h. 출력하기

노드의 순서를 출력하기 위해 List 클래스 안에 Print 함수를 작성해주고

 

cout이 제대로 작동할 수 있게 iostream도 추가해준다

 

Maze.cpp로 와서 List를 가져와 출력, 1부터 출력하기때문에 거꾸로 나옴

 

반대로 잘 출력된다

 

i. 임의의 노드 찾기 

첫번째 데이터부터 노드를 예외처리 하면서 인덱스번호까지 찾아간다

 

j. 중간 삽입/삭제의 속도가 빠른 이유

몇 번째 노드를 찾아서 삭제하는것은 느리지만 

🌟 노드의 위치를 먼저 알고 있다면 중간 삽입/삭제의 속도는 빠르다

 

1) 노드 삭제하기

 

이런식으로 가운데에 있는 node를 삭제한다고 하면

 

그냥 그 연결고리만 다시 바꿔주면 끝 

 

제거 코드 (진)

 

2) 노드 추가하기

 

이런식으로 node를 추가함

 

추가 코드 (진)

 

잘 삭제됨!!!

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -