개발 cs지식 스터디를 하며 내가 학습한 부분을 정리하는 공간입니다.

자료구조

배열(Array)

배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다.

배열을 구성하는 각각의 값을 요소(element)라고 하며,
배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.

배열은 찾고자 하는 원소의 인덱스 값을 알고 있으면 O(1)에 해당 원소로 접근할 수 있다.
즉, 랜덤 엑세스(Random Access)가 가능하다.

Array의 특징

• 배열은 논리적인 순서와 물리적인 순서가 같으므로
  인덱스를 통해 데이터에 접근할 수 있다.

• 다만 크기가 고정되어 있으므로 크기를 미리 알아야 하고,
  데이터 삽입과 삭제시 비용(cost)이 든다.

• 빈 엘리먼트를 허용하고, 중복 엘리먼트가 허용된다.

Array 단점

배열은 원소를 삽입/삭제하는 과정에서 많은 원소를 이동시켜야 한다.

만약 첫 번째 위치에 새로운 원소를 삽입한다면,
해당 원소에 접근한 뒤(O(1)) 모든 원소들을 한 칸씩 뒤로 shift 해야 한다.

반대로 첫 번째 위치의 원소를 삭제한다면,
모든 원소들은 한 칸씩 앞으로 shift해줘야 하는 비용과 시간 복잡도가 생긴다.

연결 리스트(Linked list)

이 부분에 대한 문제점을 해결하기 위한 자료구조가 linked list이다.

각각의 원소들은 자기 자신 다음에 어떤 원소인지만 기억을 하고 있으며,
따라서 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있다.

linked list의 특징

• 항상 처음 데이터부터 찾는다.
• 크기가 유동적이므로 크기를 몰라도 되며, 데이터의 삽입과 삭제가 용이하다.
• 빈 엘리먼트를 허용되지 않고(값에 Null은 넣을 수 있음), 중복 엘리먼트가 허용된다.

linked list의 단점

하지만 원하는 위치에 삽입을 하고자 할 때
원하는 위치를 검색하는 과정에 있어 첫번재 원소부터 확인해봐야 한다는 것이다.

Array와는 달리 논리적 저장 순서와 물리적 저장 순서가 일치하지 않기 때문이다.
(삽입하고 정렬하는 것과 마찬가지)

이 과정 때문에 어떠한 원소를 삭제 또는 추가하고자 했을 때,
그 원소를 찾기 위해 시간이 추가적으로 발생하게 된다.

Summary

결국 linked list 자료구조는 search에도 time complexity(시간 복잡도)를 갖고
삽입, 삭제에 대해서도 time complexity를 갖는다.

Linked List는 Tree 구조의 근간이 되는 자료구조이며,
Tree에서 사용되었을 때 그 유용성이 드러난다.