자료구조 List

배열은 인덱스를 통해 직접 접근할 수 있다는 장점이 있지만, 배열의 데이터를 삭제했을 때 빈 공간으로 남아 메모리가 낭비될 수 있다. 리스트는 배열이 가지고 있는 인덱스라는 장점대신 메모리 효율을 취한 자료구조이다.

리스트의 특징

• 데이터가 선형적으로 연결된 sequence 구조

리스트의 종류

• 단순 연결 리스트(Simple List)
• 이중 연결 리스트(Doubly List)
• 환형 연결 리스트(Circular List)

C++ STL list

이중연결리스트이다. 벡터에 비해 순회시간이 길다는 것이 단점. 단일연결리스트를 사용하고 싶다면 forward lis를 사용하자