1. 선형 자료구조
1) 선형 자료구조란?
요소가 일렬로 나열된 형태의 자료 구조
2. 연결 리스트(linked list)
1) 연결 리스트란?
연결 리스트는 데이터를 포함한 노드를 포인터로 연결하여 공간적 효율성을 극대화한 자료구조이다.
- 각 노드는 데이터 저장 변수와 다음 노드를 가르키는 포인터로 구성
- 연결된 두 노드는 메모리 공간 상에서 연속적으로 저장되지 않음(즉, 인접한 메모리 공간에 저장되지 않음)
2) 연결 리스트의 장/단점
① 장점
- 배열에 비해 효과적인 삽입/삭제 연산
int array[5]={1,2,3,4,5};만약 array[2] 원소를 삭제할 시 idx=3, idx=4인 우너소를 앞으로 한 칸씩 당겨줘야한다.
-> 링크드 리스트의 경우 idx=1인 원소가 idx=3인 노드의 포인터로 변경해주면 된다.
② 단점
- Random access 가 불가
배열의 경우 index를 사용해 특정 위치의 원소에 바로 접근이 가능한 반면, 링크드 리스트는 특정 원소를 찾기 위해 계속해서 포인터를 사용해서 검색해야함
- 노드에 데이터 변수 뿐 아니라 포인터 변수를 함께 저장하므로 각 노드마다 추가적인 메모리 공간을 사용하게 됨
3) 연결 리스트의 종류
① Single linked list(SLL)
: next 포인터만 가짐
② double linked list
: next 포인터와 prev 포인터를 가짐
③ circular double linked list
: next 포인터와 prev 포인터를 가지며, 마지막 노드의 next포인터가 헤드 노드를 가르킴
4) 주요 함수
- push_back()
- push_front()
- pop_back()
- insert(ptr, val)
#include <iostream>
using namespace std;
int main(){
list<int> a;
for(int i=0;i<10;i++) a.push_back(i);
for(int i=0;i<10;i++)a.push_front(i);
auto it = a.begin(); it++;
// it가 a의 2번 째 원소를 가르킴
a.insert(it,1000);
for(auto it : a) cout<<it<<" ";
}Random Access는 배열이 더 효율적인 반면 데이터의 추가와 삭제는 연결 리스트가 더 빠르다.
