시간 복잡도별 그래프

ArrayList vs LinkedList

배열은 다수의 데이터를 그룹핑해서 효율적으로 관리할 수 있는 자료 구조

→ 하지만, 정적으로 사용해야하는 단점이 있다.

ArrayList와 LinkedList는 이러한 단점을 보완하기 위해 만들어진 자료 구조이다.

둘 다 기능적으로만 봤을때는 아주 비슷한 역할을 하지만, 속을 들여다보면 상당히 다르다.

• 메모리 구조의 차이 (Heap)

  객체가 인스턴스를 가지게되면, 해당 객체에 대한 메모리가 Heap에 할당이된다.

  ArrayList와 LinkedList는 메모리가 할당되는 모습이 다르다.

  ArrayList는 포함되는 요소들이 한 덩어리의 메모리 안에 나란히 저장되어, 낭비되는 공간이 거의 없고, 컴퓨터 하드웨어도 연속된 덩어리에서 종종 속도가 빠르다.

  LinkedList는 각 요소가 하나 또는 두개(양방향)의 참조가 있는 노드가 필요하며, 참조를 하기위해서는 공간을 차지한다. 메모리 여기저기 노드가 흩어져 있기때문에 하드웨어 효율이 떨어 질 수 있다.

• 기능의 차이 (add / insert/ remove)

  각 기능마다 동작에 있어 차이가 있다.

  ArrayList

  add : 사이즈에 맞게 배열을 재할당해서 배열에 값을 저장.

  insert : 사이즈에 맞게 배열을 재할당해서 삽입하고자 하는 index 기준으로 오른쪽으로 한칸씩 요소들을 Shift한 뒤, 값을 index에 저장.

  remove : index 기준으로 왼쪽으로 한칸씩 요소들을 Shift하여 해당 index의 값을 대입을 통해 삭제한다.

  LinkedList

  add : 시작 노드부터 다음 노드로 이동하면서 제일 끝 노드를 찾아 연결한다.

  insert : 시작 노드부터 삽입하고자 하는 index 만큼 이동한 뒤 노드를 연결해준다.

  remove : 시작 노드부터 삭제하고자 하는 index만큼 이동한 뒤 노드를 끊어준다.

• 선택 기준

  상황 별 기능 성능

  → 응용 프로그램의 실행 시간이 get과 set 메소드에 의존한다면, ArrayList가 좋다.

  반대로, 시작이나 끝 요소에 추가하는 연산에 의존한다면, LinkedList(양방향)가 좋다.

  이러한 연산이 프로그램 실행 시간에 뚜렷한 영향을 미치지 않는다면, 즉 응용 프로그램이 다른 일을 하느라 대부분의 시간을 소비하면 List 구현에 대한 선택은 큰 의미가 없다고한다.

  하지만, 시간에만 초점을 두지말고, 공간적인 부분을 생각했을 때에는 요소가 많을수록 ArrayList가 더 효율적일 수 있다.

  Queue (큐)

  

  리스트의 한쪽 끝에서는 원소들이 삭제되고 반대쪽 끝에서는 원소들의 삽입만 가능하게 만든 순서화된 리스트이다. (First In First Out 형식)

  Deque (덱)

  

  큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 큐와 스택의 성질을 모두 가지고 있는 자료구조이다.

  HashMap

  • Map

    Map은 Key와 Value 쌍(Pair)을 이용하여 데이터를 관리할 수 있는 자료 구조

    저장 시, Key로 접근이 가능한 곳에 Value를 저장한다.

    Value의 값을 얻고 싶다면, 같은 쌍인 Key를 전달해야 얻을 수 있다.

    

  • Hash

    해시함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.

    — 매핑 전 원래 데이터의 값을 키(key)

    — 매핑 후 데이터의 값을 해시값(hash value)

    — 매핑하는 과정을 해싱(hashing)

    → 즉, HashMap은 Key를 해싱하여 얻어진 해시값을 Index로 사용하는 Map이다.

    [해시 활용 예시]

    중복없는 유니크한 정보가 필요할 때

    — git commit 정보

    — 블록체인(많은 양의 거래 기록을 보관할 때, 용량을 줄일 수 있다.)

    데이터가 훼손되지 않음을 보장해야 할 때 (무결성)

    — 전자서명

    — 인증용 토큰(JWT)에서의 서명

    브라우저 로컬 스토리지

    — 간단한 키와 값을 저장할 수 있다. 키-밸류 스토리지의 형태

    로컬 스토리지 데이터는 사용자가 지우지 않는 이상 계속 브라우저에 남아 있음 .

    → 세션 스토리지 데이터는 윈도우나 브라우저 탭을 닫을 경우 제거.

    → 쿠키는 만료 기한이 있는 키-값 저장소

    [주의해야할 점]

    다른 입력이지만 같은 해시값이 나오는 경우가 있을 수 있다. (충돌 Collison)

    → 중복이 적게 나타날 수록 좋은 해시함수

  • Hash 충돌 방지

    Chaining

    — Main Bucket이 존재하며, 충돌이 발생하는 경우를 대비하여 Sub Bucket들이 존재한다.

    SubBucket은 Linked List 나 배열을 통해 구현할 수 있다.

    Sub Bucket에 Entry가 존재하는데, 충돌이 발생한 경우 해당 Entry의 다음에 연결한다.

    

    Open addressing

    — Chaining 방식과는 다르게 Bucket 당 들어갈 수 있는 엔트리는 한개이며, 해시 충돌 시 다른 주소에 저장함으로써 충돌을 방지한다. 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용하는 방법으로, Separate chaining 방식에 비해서 메모리를 덜 사용한다.

  TreeMap

  TreeMap은 이름에서 유추할 수 있듯이, 이진 트리 구조로 구성되어 있다.

  부모 노드를 기준으로 자식 노드의 값이 큰 것들은 오른쪽, 작은 것들은 왼쪽으로 나뉘어진다.

  

  이러한 구조의 특징으로 부모 노드를 기준으로 절반의 노드를 고려하지 않고 다른 절반의 노드에서 재귀적으로 탐색하기 때문에 전체 노드를 고려하여 검색하는 것보다 속도가 빠르다.