선형자료구조

1. 동적배열

- 원소를 순서대로 저장 --> 인덱싱(원소찾기)이 O(1)
- 삽입, 삭제 O(N)

- 원소들이 메모리에 연속해 배치되어 있어 CPU 캐시의 효율을 높여줍니다.

 

capacity: 미리 여유있게 할당받은 메모리의 크기 = 배열의 용량

size: 배열의 원소 수

용량(capacity)이 꽉찼을 때, 배열에 새로운 원소를 추가하려면

아래 방식으로 재할당을 하여야 합니다.

더 큰 새 배열을 동적으로 할당받고,
기존 배열의 내용을 모두 복사한 다음,
배열에 대한 포인터를 바꿔치기(swap)해야 합니다.

- append() 연산과, 성능

 

 append() 연산을 여러번 할 때 배열의 최종크기가 얼마일지 미리 짐작할 수 있다면,

동적배열의 용량을 미리 늘려둠으로써 재할당 비용을 없앨 수 있습니다. --> 속도 최적화

C++ vector 에서는 reserve()
java ArrayList 에서는 ensureCapacity() 로 가능

 

2. 연결리스트

- 삽입, 삭제 --> O(1)
- 검색 O(N)

- 원소들이 메모리 여기저기에 흩어져있고, 포인터로 이어져 있음.

 

구조체(혹은 클래스)를 만들어 node를 표현

struct ListNode {
    int element;
    ListNode *prev, *next;
}

 

 

표준라이브러리에 있음

C++ STL의 list
java, C#의 LinkedList

 

 

그 외 응용 연산

splicing: 리스트를 잘라 다른 리스트에 이어 붙임 --> O(1)
하지만, 리스트 전체의 크기를 아는데 O(N)시간이 걸릴 수 있음.
삭제 했던 원소 돌려놓기, recoverNode()
응용: undo(되돌리기), 조합탐색에서의 되살리기(Dancing Links)