ArrayList

  • 사이즈가 고정되어 있음
  • 삽입 시 사이즈를 늘려주는 연산이 필요
  • 삭제 시에는 순차적인 인덱스 구조로 인해서 삭제된 빈 인덱스를 채워야 하기때문에 채워주는 연산이 필요
  • 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 이런 부가적인 연산이 시스템의 성능 저하로 이어져 치명적임


LinkedList

  • 뒤로 밀거나 채우는 작업 없이 단지 주소만 서로 연결시켜 주면 되기 때문에 추가/삭제가 ArrayList보다 빠르고 용이
  • 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직


LinkedList의 단점

  • ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만 가능
  • LinkedList는 단방향성을 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않음
  • 사실 순차 접근도 참조의 지역성(locality of reference) 때문에 LinkedList 보다는 ArrayList가 훨씬 빠름
    • n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장
    • LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됨
    • 참조자를 위해 추가적인 메모리를 할당해야 하므로 자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가 적인 메모리할당은 비실용적일 수 있음


Double LinkedList

  • 기존의 링크드리스트는 단방향으로만 탐색할 수 있으나 더블링크드리스트는 앞의 노드의 주소도 가지고 있으므로
    양방향 탐색이 가능


참조의 지역성:  전산 이론중의 하나로 한번 참조한 데이터는 다시 참조될 가능성이 높고 참조된 데이터 주변의 데이터 역시 같이 참조될 가능성이 높다는 이론


Reference


저작자표시 비영리 변경금지

선형/비선형 자료구조

  • 선형 자료구조
    • 리스트, 스택, 큐와 같이 데이터 집합을 한 줄로 늘어 세운 구조
  • 비선형 자료구조
    • 트리(Tree)는 데이터 집합을 여러 갈래로 나누어 세운 비선형 구조
    • 삽입, 삭제, 검색에 대해서 선형 구조보다 나은 시간적 효율을 보임


트리

  • 일반트리


  • 이진트리
    • 최대 두 개까지의 자식노드를 가질 수 있는 트리


일반트리의 이진트리 변환

  • 일반트리에서는 자식노드의 수가 몇 개가 있는지 예측 불가하여 컴퓨터로 표현하기 어려움
  • 모든 일반 트리는 이진 트리로 바꾸어 표현 가능
  • 왼쪽자식노드-오른쪽형제노드 방법



이진트리의 종류

  • 포화 이진트리
    • 리프노드를 제외한 모든 노드의 자식은 2개
  • 완전 이진트리
    • 모든 노드의 자식은 0개 또는 2개
  • skew 이진트리
    • 한 쪽으로 치우친 트리


이진트리의 저장

  • 배열
    • 완전 이진트리의 경우

    • skewed 이진트리의 경우


    • 배열의 단점
      • 배열의 이용하지 않는 저장 공간이 많다.
      • 트리의 최대 깊이를 대비하여 기억장소를 확보하기 때문에 메모리 사용량이 많고, 확보한 기억장소보다 트리를 확장할 수 없다.
  • 링크드리스트


이진트리의 순회(Traversal)


  • 전위순회(Preoder Traversal)
    • 방문 순서:  G, C, A, E, L
void PreOrder (Nptr T) {
	if (T != NULL) {
		Visit(T->Name);
 		PreOrder(T->LChild);
		PreOrder(T->RChild);
	}
}


  • 중위순회(Inoder Traversal)
    • 방문 순서:  A, C, E, G, L
void InOrder (Nptr T) {
	if (T != NULL) {
		InOrder(T->LChild); 
		Visit(T->Name);
		InOrder(T->RChild); 
	} 
}


  • 후위순회(Postorder Traversal)
    • 방문 순서:  A, E, C, L, G
void PostOrder (Nptr T) {
	if (T != NULL) {
		PostOrder(T->LChild); 
		PostOrder(T->RChild); 
		Visit(T->Name);
	} 
}


Reference


저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바