강의보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린점이 있을 수 있음에 양해부탁드립니다. (피드백 환영입니다)

선형과 비선형

선형 구조는 자료를 순차적으로 나열한 형태

• 배열
• 연결 리스트
• 스택 / 큐

비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

• 트리
• 그래프

배열 vs 동적 배열 vs 연결 리스트

배열

• 사용할 방 개수를 고정해서 계약하고 (절대 변경 불가)
• 연속된 방으로 배정 받아 사용

장점으로는 연속된 방이라는 것이고
단점으로는 방을 추가/축소가 불가하다.

동적 배열

• 사용할 방 개수를 유동적으로 계약
• 연속된 방으로 배정 받아 사용

문제점으로는 이사 비용이 높음
그래서
동적 배열 할당 정책을 사용함

• 실제로 사용할 방보다 많이, 여유분을 두고 (대략 1.5~2배) 예약
• 이사 횟수를 최소화

장점으로는 유동적인 계약이 가능하다는 것(방 여유분 추가 예약으로 이사 횟수 최소화)이고
단점으로는 중간 삽입과 삭제에서 좋지않다.

연결 리스트

• 연속되지 않은 방을 사용

장점으로는 중간 삽입과 삭제에서 이점이 있다.
단점으로는 N번째 방을 바로 찾을 수가 없다 (임의 접근 Random Access 불가)

임의 접근

• N번째 방이 몇 번 방인지 바로 찾을 수 있는지

우리가 2번째 방을 찾으려면 시작 지점에서 이동을 해야하기 때문에 느리다.
동적 배열같은 경우에는 서로 연속되어 있기때문에 빠르게 찾을 수 있다.

하지만 연결 리스트는 위치를 알고있다면 굉장히 빠르게 찾을 수 있다.

정리

일반적으로 실전에서는 대부분 동적배열을 사용한다.
하지만 동적 배열과 연결 리스트의 차이를 알아야 하고
연결 리스트를 구성하는 핵심 기법들이 나머지 자료구조에도 사용이 되기 때문에 많은 도움이 된다.

만약 코드로 구현해본걸 보고 싶다면 (배열[Array], 동적 배열[Vector], 연결 리스트[List])
코드 저장소
여기 내 깃허브 레포에 들어가서 RooKissClass -> ALL IN ONE -> Data Structure -> Maze에 들어가서 보면 된다