자료 구조 정리

Park Jae Hong·2022년 10월 3일
0

연결 리스트(Linked List)

: 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. (크기가 동적인 자료구조)

(삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸립니다.

종류

  • 싱글 연결 리스트
    : next 포인터만 가진다.

  • 이중 연결 리스트
    : next 포인터와 prev 포인터를 가진다.

  • 원형 이중 연결 리스트
    : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가르킨다.

벡터(Vector)

: 동적으로 요소를 할당할 수 있는 동적 배열

Vector vs ArrayList

: 먼저, Vector와 ArrayList는 동일한 내부 구조를 가지고 있다.

public class Vector<E> extends AbstractList<E> 
		implements List<E>, RandomAccess, Cloneable, Serializable {
}

public class ArrayList<E> extends AbstractList<E> 
		implements List<E>, RandomAccess, Cloneable, Serializable {
}

위와 같이 같은 Class나 Interface를 상속받는 것을 볼 수 있다.

차이점 ?

  • 동기화
  1. Vector는 한번에 하나의 스레드에서만 접근이 가능
  2. ArrayList는 동시에 여러 스레드에서 작업이 가능하다 (때문에 ArrayList를 사용할 때는 명시적으로 동기화가 필요하다.)
  • 크기
  1. Vector는 기존 용량의 100% (2의 N+1승 만큼 증가)
  2. ArrayList 기존 용량의 50%
  • 성능
    : 동기화 되지 않는 ArrayList가 성능이 좋다

Vector를 사용하지 않는 이유 ?

  • 완전한 동기화
    : ArrayList와의 차이점이 동기화가 된다는 것인데, 사실 Vector는 완전한 동기화가 되지 않는다. 작업간의 동기화는 가능하지만 전체적으로 동기화 하지 않는다. 그러므로 성능이 좋은 ArrayList를 사용.

그렇다면 왜 Vector는 없어지지 않는 것일까 ?

: Vector는 JDK1.0 부터 사용해 오던 Class 이다. 그래서 Vector를 상속 받는 Class들이 많아 호환성을 위해 아직 존재하고 있다.

profile
The people who are crazy enough to think they can change the world are the ones who do. -Steve Jobs-

0개의 댓글