Vector, ArrayList, LinkedList

 

 

 

---

 

Vector, ArrayList, LinkedList의 차이는 무엇일까?

 

 

---

 

 

 

 

Vector

 

--

List 인터페이스를 구현한 클래스로

순서를 유지하고, 중복 요소를 허용하는 컬렉션이다.

 

특징

• 동기화를 지원하는 list 구현 클래스
• 내부적으로 동적 배열을 사용하여 데이터를 관리
• 배열이 가득 차면 기존 용량의 2배로 증가시킨다.

 

간단하게 설명하자면

Vector는 그냥 객체 저장용 배열이다.

 

동적 배열이어도 배열이기 때문에

크기를 변경하려면 새로운 배열을 생성 후, 데이터를 복사하고 주소를 옮겨서 증가시키는 것처럼 보이게 한다.

그래서 처음부터 충분한 배열 크기를 생성하여 사용해야 좋다.

 

동기화는 멀티스레드 환경에서만 필요한 것으로

싱글스레드 환경에서 vector를 사용하게 되면 성능이 떨어지게 된다.

그리고 동기화 오버헤드로 인해 현재는 잘 사용하지 않는다.

--

 

 

 

 

ArrayList

 

--

ArrayList는

기존의 Vector를 개선한 클래스로 구현원리와 기능적으로는 동일하지만

큰 차이점이 있다면 "동기화"를 지원하지 않기 때문에

Vector와 다르게 싱글스레드 환경에서 성능이 뛰어나다.

 

특징

• 동기화를 지원하지 않아서 싱글 스레드 환경에서 빠르다.
• 내부적으로 동적 배열 사용
• 용량이 가득 차면 기존 용량의 1.5배 증가

 

기본적으로 동기화를 지원하지 않기 때문에
멀티스레드 환경에서는 안전하지 않다.
(별도로 동기화 작업을 해줘야 한다.)

--

 

 

 

 

LinkedList

 

--

LinkedList는

Vector와 ArrysList에서 사용하는 배열 방식을 보완한 방법으로

개별적인 데이터들을 서로 연결하여 나열하는 방식을 사용한다.

 

그래서 배열의 큰 단점인

• 크기 변경 불가능
• 데이터 추가, 삭제에 걸리는 시간이 오래 걸림

을 보완할 수 있게 된다.

 

 

위 그림처럼 하나의 데이터 덩어리(객체)를 "노드(Node)"라고 부르고

해당 노드 안에는 "다음 노드 주소"와 "데이터"가 담겨 있다.

 

노드 객체 기본 형식

class Node {
    Node next;
    Object obj;
}

 

 

 

데이터를 삭제하고 싶다면?

삭제할 노드의 이전 노드에서 다음 노드의 주소를

삭제할 노드의 다음 노드 주소로 변경해 주면 된다.

즉, 한 번의 참조 변경만으로 삭제가 가능해진다.

 

 

데이터를 추가하고 싶다면?

추가할 노드객체를 생성하고

추가할 위치의 이전 노드에서 다음 노드의 주소를 새로 추가할 노드 주소로 변경하고

생성한 노드에서 다음 노드 주소에 추가할 위치의 다음 노드 주소를 작성하면 된다.

즉, 한 번의 노드객체 생성과 두 번의 참조변경만 해주면 된다.

--

 

 

 

 

DoublyLinkedList (이중 연결 리스트)

 

--

기존 LinkedList는 단 방향으로만 접근이 가능하여 데이터의 접근성이 좋지 않았지만

양방향(단방향+단방향)처럼 연결하여 해당 단점을 보완할 수 있다.

 

 

노드객체에서 이전 노드 주소를 가리키는 값도 추가되었다.

그래서 노드객체를 추가, 삭제할 때 변경해야 하는 참조가 더 늘었다.

 

노드 객체 기본 형식

class Node {
    Node next;
    Node previous;
    Object obj;
}

 

기존 노드에서 노드객체를 가리키는 값에서 null 또한 이어서 다음 주소를 넣어서
원형 연결리스트 형식으로 구현할 수도 있다.

--

 

 

 

 

LinkedList 메서드 정리

 

--

객체 생성

 

 

요소 추가 / 삽입

 

 

요소 삭제

 

 

요소 검색

 

 

요소 반환

 

 

요소 변경

 

 

배열 변환

 

 

이터레이터(Iterator) 반환

 

 

스택 & 큐

리스트 용도뿐 아니라 구조 특성상 "스택, 큐"로도 사용이 가능하다.

--