[Java] ArrayList | LinkedList

Jeini·2022년 12월 4일

☕️ Java

목록 보기

38/59

💡 ArrayList

ArrayList는 기존의 Vector를 개선한 것으로 구현원리와 기능적으로 동일하다.

ArrayList와 달리 Vector는 자체적으로 동기화처리가 되어 있다.

List 인터페이스를 구현하므로, 저장순서가 유지되고 중복을 허용한다.

데이터의 저장공간으로 배열을 사용한다. (배열 기반)
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializale {
	...
    protected Object[] elementData; // 객체를 담기 위한 배열
	...
}

ArrayList 클래스는 가장 많이 사용되는 컬렉션 클래스 중 하나이다.
JDK 1.2부터 제공된 ArrayList 클래스는 내부적으로 배열을 이용하여 요소를 저장한다.

ArrayList 클래스는 배열을 이용하기 때문에 인덱스를 이용해 배열 요소에 빠르게 접근할 수 있다.

하지만 배열은 크기를 변경할 수 없는 인스턴스이므로, 크기를 늘리기 위해서는 새로운 배열을 생성하고 기존의 요소들을 옮겨야 하는 복잡한 과정을 거쳐야 한다.

✏️ ArrayList 생성자

✔️ String class / Collection_List의 생성자, 메서드의 기능이 유사하기 때문에 간단요약함.

❗️ initialCapacity: 배열의 용량

✏️ ArrayList 메서드

📎 추가

❗️ int index: 저장위치

📎 삭제

❗️ void clear(): 모든 객체 삭제

📎 검색

❗️ 못찾으면 -1 반환
❗️ Object set(int index, Object element): 변경

📎 그 외

❗️ int size(): 저장된 객체의 갯수

💡 LinkedList

LinkedList를 들어가기 전에 배열의 장단점을 한번 더 정리하고 들어가자.

📎 배열의 장단점

❗️ 장점

배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근기간, access time)이 짧다.
배열은 연속적이기 때문에 배열주소를 쉽게 계산할 수 있다.

❗️ 단점

크기를 변경할 수 없다.
: 크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사해야 한다.
: 그래서 내가 예상하는 객체의 갯수를 예상한 다음 처음부터 크기를 넉넉하게 잡아주는 것이 좋다.
1. 더 큰 배열생성
2. 복사
3. 참조 변경
비순차적인 데이터의 추가, 삭제에 시간이 많이 걸린다.
: 데이터를 추가하거나 삭제하기 위해, 다른 데이터를 옮겨야 한다.
: 그러나 순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠르다.

❗️배열의 단점을 보완하는 LinkedList

이러한 배열의 단점을 보완해주기 위해 LinkedList가 만들어 졌다.

배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결한다.
: 바로 옆에 있을 수도 있고 멀리 떨어져있을 수도 있다는 것.
단 한 번의 참조변경만으로 데이터 삭제가 가능하다.

📎 Singly linkedList

class Node { // 요소 하나하나가 Node를 의미한다.
	Node next; //  다음노드가 어딘지 참조노드를 가르키게 된다.
    Object obj; // 데이터
}

class SinglyLinkedNode {
    int val;
    SinglyLinkedNode next = null;
    SinglyLinkedNode(int v) {
        val = v;
    }
}

✔️ 단일 연결 리스트(singly linkedList)
: 다음 요소를 가르키는 참조만을 가지는 연결 리스트

요소의 저장과 삭제 작업이 다음 요소를 가리키는 참조만 변경하면 되므로, 아주 빠르게 처리될 수 있다.
연결리스트, 데이터 접근성 낮음
: 현재 요소에서 이전 요소로 접근하기가 매우 어렵다.

📎 doubly linkedList

class Node {
	Node next; // 다음요소
    Node previous; // 이전요소
    Object obj; // 데이터
}

class DoublyListNode {
    int val;
    DoublyListNode next;
    DoublyListNode prev;
    DoublyListNode(int x) {
    	val = x;
    }
}

✔️ 이중 연결 리스트(doubly linked list)
: 이전 요소를 가리키는 참조도 가지는 연결 리스트

이중 연결리스트, 접근성 향상
: 연결이 2개 ➡️ 다음요소와 이전요소 총 참조를 2개 가지고 있다.
추가 삭제할 때에는 2개의 연결을 끊어줘야하기 때문에 시간이 좀 더 걸린다.
하지만 여전히 한번에 2개 3개 건너뛰는것은 불가능하다.

📎 doubly circular linkedList

✔️ 이중 원형 연결리스트(doubly circular linkedList)

마지막 요소를 맨 처음 요소에, 맨 처음 요소를 맨 끝의 요소로 연결할 수 있다.

맨 처음요소에서 맨 끝의 요소를 이동할 때 하나하나 다음 노드로 이동해야 하는 것을 앞에서 바로 맨 끝으로 이동 할 수 있다.

예를 들어, 채널 1에서 리모컨으로 채널을 감소시킬 때, 채널0이 되는 것이 아니라 채널 999인 젤 마지막 채널로 향한다. 이런 원리와 마찬가지이다.

💡 ArrayList VS LinkedList

1. 순차적으로 추가하기

ArrayList: 406
LinkedList: 606

LinkedList는 새로운 객체를 하나하나다 만들기 때문에 배열보다는 추가가 느리다.

2. 순차적으로 삭제하기

ArrayList: 11
LinkedList: 46

3. 중간에 추가하기

ArrayList: 7382
LinkedList: 31

4. 중간에서 삭제하기

ArrayList: 6694
LinkedList: 380

5. 접근시간테스트

ArrayList: 1
LinkedList: 432

순차적으로 데이터를 추가 / 삭제: ArryaList가 빠름

비순차적으로 데이터를 추가 / 삭제: LinkedList가 빠름

접근시간(access time): ArrayList가 빠름
index가 n인 데이터의 주소 = 배열의 주소 + n * 데이터 타입의 크기