TIL Day54 자료구조

선형

• 배열(Array) : 동일한 타입의 데이터를 순차적으로 저장하는 자료구조
• 리스트 (List) : 순서가 있는 데이터를 저장하는 자료구조, ArrayList, LinkedList, Vector 등
  • ArrayList : [배열에 비해 데이터를 삽입, 삭제가 자유롭고 배열처럼 정보를 찾아냄에 있어 이점이 많아 사용한다] ArrayList란 Collection 프레임워크의 일부이며 java.util 패키지에 소속되어 있습니다 표준 배열보다는 느리지만 배열에서 많은 조작이 필요한 경우 유용하게 사용할 수 있습니다 List 인터페이스에서 상속받아 사용이 됩니다 ArrayList는 객체가 추가되어 용량을 초과하면 자동으로 부족한 크기만큼 용량이 늘어납니다
    
  • Linked List : 연속된 메모리 공간에 저장되어 있지 않음. 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재함. 그리고 이 노드는 자신의 앞에 있는 데이터와 뒤에 있는 데이터에 대한 주소를 기억하고 있음.
    • (자료의 생성 , 삭제가 array에 비해서 쉽다. 하지만 검색을 하여 정보를 찾아야 하는 경우 array 와 같은 index가 없기 때문에 차이가 있다. )
    • 참고한 사이트 arraylist와 linkedList 비교

Array와 LinkedList의 차이

맵 (Map) : key - value로 데이터를 저장하는 자료구조, HashMap, TreeMap, LinkedHashMap 등

• HashMap
  • key - value를 하나의 데이터(entry)로 저장한다.
  • hashcode를 사용하기 때문에 예측할 수 없는 순서로 저장된다. (TreeMap과 차이점)
  • key는 중복되지 않지만 값은 중복이 될 수 있다. 기존에 저장된 key로 값을 저장하면 기존 값은 없어지고 새로운 값이 저장된다.
  • hashing을 사용하기 때문에 많은 양의 데이터를 검색할 때 성능이 좋다.
  • 해시 함수를 통해 매핑된 해시를 Index로 활용하기 때문에 데이터에 대한 검색, 삽입, 제거 연산의 시간 복잡도가 O(1)이라는 확실한 장점이 있다.
• TreeMap
  • key 값에 따라서 자동으로 Sort가 된다.
  • 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 오름차순 정렬한다.
  • HashMap과는 다르게 key 값으로 null을 허용하지 않는다.
  • 데이터를 저장할 때 즉시 정렬하기 때문에 추가나 삭제가 HashMap 보다 오래 걸린다.
    
• 셋 (Set) : 순서가 없는 데이터를 중복 없이 저장하는 자료구조, HashSet, TreeSet 등
• 스택 (Stack) : 후입선출 구조를 갖는 자료구조, push()와 pop() 메소드를 이용하여 데이터를 추가하고 삭제함(FILO : First In Last Out)
• 큐 (Queue) : 선입선출 구조를 갖는 자료구조, Enqueue(), Dequeue() 메소드를 이용하여 데이터를 추가하고 제거함(FIFO: First In First Out)
• 덱 (Deque) : 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조, LinkedList 등
  • 큐의 자료구조형을 양방향에 가능 하게 만든 자료구조라고 생각 하면 편하다.

비선형

• 트리 (Tree) : 계층적 구조를 갖는 자료구조, 이진트리, 이진탐색트리, AVL 트리, 레드 블랙 트리 등
  • 이진 트리 : 자식 노드가 최대 2개인 노드들로 구성된 트리
    • 전위 순회, 중위 순회, 후위 순회를 통해 탐색할 수 있다. (https://code-lab1.tistory.com/9 참고)
    • 이진 탐색 트리 : 이진 탐색 + LinkedList를 결합한 이진 트리
      • 트리의 높이가 h라면 O(h)의 복잡도를 가지게 된다.
      • 이진 트리보다 탐색이 빠르다.
      • 트리 안에 찾고자 하는 값이 없더라도 최대 h번의 연산 및 탐색이 진행된다.

  ---

• 그래프 : 노드와 노드 간을 연결하는 간선으로 구성된 자료구조, 이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조
  
• 트리와 그래프의 차이점

  	트리	그래프
  정의	그래프의 한 종류, 방향성이 있는 비순환 그래프	노드와 노드를 연결하는 간선으로 구성된 자료구조
  방향성	방향 그래프만 존재	방향, 무방향 모두 존재
  사이클	비순환 그래프만 존재	순환, 비순환 모두 존재.
  노드 한개의 자체 순환도 가능.
  루트 노드	한 개의 루트 노드만이 존재	루트 노드의 개념이 없음
  부모 - 자식	루트 노드를 제외한 노드는 1개의 부모 노드만을 가짐	부모 - 자식 개념이 없음
  모델	계층 모델	네트워크 모델
  순회	DFS, BFS 방식의 전위, 중위, 후위 순회	DFS, BFS
  간선의 수	N개의 노드를 가진 트리는 항상 N - 1개의 간선을 가짐	간선의 개수는 자유, 없을 수도 있음
  경로	임의의 두 노드 간의 경로는 유일
  예시 및 종류	이진 트리, 이진 탐색 트리, 레드 블랙 트리, 이진 힙	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 선수 과목