선형 자료구조 기초

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

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

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

• 트리
• 그래프

 

1. 배열 (STL Array)

• 메모리 크기 고정(절대 변경 불가), 연속된 주소
• 장점 : 연속된 메모리
• 단점 : 메모리 추가/축소 불가

2. 동적 배열(vector)

• 메모리 크기의 여유분을 두고(1.5배~2배) 설정, 연속된 주소
• 만약 여유분이 다 차면, 다같이 연속된 메모리위치로 이사 (여유분의 이유 : 이사횟수를 최소화하기 위해)
• 장점 : 유동적인 삽입(메모리 여유분 추가 예약으로 이사 최소)
• 단점 : 중간 삽입 / 삭제 할 경우 나머지가 옆으로 이동해야함

동적 배열 구현

• 벡터 사용시 헤더 <vector> 추가
• push_back : 현재 저장된 데이터 크기(size) 와 할당된 메모리 크기(capacity)를 비교해서 메모리 추가(reserve함수) 후 데이터 저장

• resize : size를 임의로 조정
  • 조절한 size < capacity : 그대로 유지
  • 조절한 size > capacity : capacity 증가
• reserve : capacity를 조절

3. 연결리스트(list)

• 연속되지 않은 메모리를 사용, 각 주소기준 양옆으로 접근 가능
• 장점 : 중간 삽입 / 삭제 유용 (이사비용이 없다)
  • 단, 이 경우는 iterator을 사용해서 위치를 알고 있을 때만 적용된다. 만일 리스트만 가지고 있다? 절대 빠르지 않다. head부터 탐색하기 때문.
• 단점 : N번째 메모리 주소를 바로 찾을 수 없음(임의 접근 Random Access 불가)

연결리스트 구현

연결리스트는 크게 Node, Iterator, List를 구현하는데, 여기선 List의 AddNode(), RemoveNode()만 올려보려고 한다.

연결 리스트에서 가장 핵심적이고, Node와 Iterator에서도 사용되는 개념인 " → "

기본적으로 양방향 리스트 기준 [head] ↔  [tail] 이고, prev와 next를 통해 앞뒤 노드에 접근한다.

 

위 코드도 노드를 추가할 때, 삭제할 때 앞뒤 노드의 연결을 새로 맺고 끊음으로서 연결리스트를 구현한다.