programming language/Java

Deque, LinkedList 와 ArrayDeque

공대키메라 2022. 4. 11. 21:47

이번 시간에는 Deque 인터페이스를 알아보고 이의 구현체인 LinkedList와 ArrayDeque를 알아보고 비교할 것이다. 

 

출처 : https://programiz.xyz/-/deque-interface-in-java/

1. Deque란?

원소의 추가와 삭제를 둘 다 끝부분에서 지원하는 선형 collection.

Deque라는 이름은 double ended queue의 줄임말이고 주로 "deck"으로 발음된다.

대부분의 Deque(Double eneded queue) 구현체는 Deque가 포함하고 있는 원소의 수에 고정된 제한이 없다. 하지만, 이 인터페이스는 고정된 사이즈 제한을 가진 것들과 마찬가지로 용량 제한(capacity-restricted) deque를 지원한다.

이 인터페이스는 deque의 끝부분 둘 다에 접근하는 메소드를 정의한다.

insert, remove, examine이 제공된다.

각각의 메소드들은 두개의 형태로 존재한다.

(하나의 형태는 실패하면 exception 을 던지거나, 특별한 값을 반환하거나 - 작업에 따라서 true 혹은 false나 null 등등 - , insertion 메소드의 다른 하나의 형태는 특별히 용량 제한 deque 의 구현체로 디자인되었고 insert 작업은 실패할 수 없다.)

 

그리고 친절하게 어떤 결과에 대하 어떤 값을 반환하는지 2개의 형태로 나누어서 마지막 부분의 설명을 이어간다.

 

Deque 메소드 요약

  First Element (Head) Last Element (Tail)
  Throws exception Special value Throws exception Special value
Insert addFirst(e) offerFirst(e) addLast(e) offerLast(e)
Remove removeFirst() pollFirst() removeLast() pollLast()
Examine getFirst() peekFirst() getLast() peekLast()

 

Deque 메소드 설명 더보기 클릭!

더보기

Modifier and TypeMethod and Description

boolean add(E e)
Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
void addFirst(E e)
Inserts the specified element at the front of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available.
void addLast(E e)
Inserts the specified element at the end of this deque if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available.
boolean contains(Object o)
Returns true if this deque contains the specified element.
Iterator<E> descendingIterator()
Returns an iterator over the elements in this deque in reverse sequential order.
E element()
Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque).
E getFirst()
Retrieves, but does not remove, the first element of this deque.
E getLast()
Retrieves, but does not remove, the last element of this deque.
Iterator<E> iterator()
Returns an iterator over the elements in this deque in proper sequence.
boolean offer(E e)
Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and false if no space is currently available.
boolean offerFirst(E e)
Inserts the specified element at the front of this deque unless it would violate capacity restrictions.
boolean offerLast(E e)
Inserts the specified element at the end of this deque unless it would violate capacity restrictions.
E peek()
Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
E peekFirst()
Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
E peekLast()
Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
E poll()
Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
E pollFirst()
Retrieves and removes the first element of this deque, or returns null if this deque is empty.
E pollLast()
Retrieves and removes the last element of this deque, or returns null if this deque is empty.
E pop()
Pops an element from the stack represented by this deque.
void push(E e)
Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, throwing an IllegalStateException if no space is currently available.
E remove()
Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque).
boolean remove(Object o)
Removes the first occurrence of the specified element from this deque.
E removeFirst()
Retrieves and removes the first element of this deque.
boolean removeFirstOccurrence(Object o)
Removes the first occurrence of the specified element from this deque.
E removeLast()
Retrieves and removes the last element of this deque.
boolean removeLastOccurrence(Object o)
Removes the last occurrence of the specified element from this deque.
int size()
Returns the number of elements in this deque.

 

2. LinkedList란?

List 와 Deque인터페이트의 양방향 링크 리스트의 구현체. 모든 성분을 허용하고 optional list operation을 구현한다. 

모든 작동은 양방향 링크 리스트로 예상할 수 있다. 리스트 안에 indexing한 operations들은 list를 특정 index에 더 가까운 어느쪽이든 시작부터 끝까지 가로지른다.

출처 : https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

 

oracle 사이트 설명은 정말 알아먹기가 힘들다. 무엇보다도 operations들을 뭐라고 해석해야 깔끔할지 모르겠다.

 

그래서 다른 글을 또 가져왔다.

 

LinkedList는 컨테이너에 아이템들을 저장한다. 

리스트는 첫번째 컨테이너에 링크를 가지고 각각 컨테이너는 리스트의 다음 컨테이너에 링크를 가진다.

리스트에 원소를 추가하려면, 원소는 새로운 컨테이너에 놓이고, 그 컨테이너는 리스트 안의 다른 컨테이너 중 하나와 연결된다. 

출처 : https://www.w3schools.com/java/java_linkedlist.asp

 

내용을 읽어보니 다음 그림을 설명하는 것 같다. 

 

출처 : https://coding-factory.tistory.com/552

 

그리고 양방향으로 이어져 있으니 양방향 노드를 생각하면 될 것이다.

출처 : https://velog.io/@underlier12/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%99%EC%8A%B5-03-kek5cinu4d

더보기

Constructor and Description

LinkedList()
Constructs an empty list.
LinkedList(Collection<? extends E> c)
Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

Modifier and TypeMethod and Description

boolean add(E e)
Appends the specified element to the end of this list.
=> 리스트의 마지막에 특정 성분을 추가한다. 
void add(int index, E element)
Inserts the specified element at the specified position in this list.
=> 리스트의 특정 위치에 특정 성분을 삽입한다.
boolean addAll(Collection<? extends E> c)
Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
=> 특정 컬렉션의 iterator에 의해 반환된 것을 위해 리스트의 끝에 특정 콜렉션의 모든 성분을 추가한다. 
boolean addAll(int index, Collection<? extends E> c)
Inserts all of the elements in the specified collection into this list, starting at the specified position.
=> 특정 위치에서 시작해서 리스트안의 특정 콜렉션의 모든 성분을 삽입한다. 
void addFirst(E e)
Inserts the specified element at the beginning of this list.
=> 리스트 시작부분에 특정 성분을 삽입한다.
void addLast(E e)
Appends the specified element to the end of this list.
=> 리스트 끝에 특정 성분을 추가한다. 
void clear()
Removes all of the elements from this list.
=> 리스트의 모든 성분을 제거한다.
Object clone()
Returns a shallow copy of this LinkedList.
=> LinkedList의 얕은 복사를 반환한다.
boolean contains(Object o)
Returns true if this list contains the specified element.
=> 특정 성분을 포함한지 여부를 반환
Iterator<E> descendingIterator()
Returns an iterator over the elements in this deque in reverse sequential order.
=> 뒤집힌 연속 순서로 deque에서 iterator가 성분들을 반환한다. 
E element()
Retrieves, but does not remove, the head (first element) of this list.
=> 리스트의 첫번째 성분을 반환한다.(삭제 x)
E get(int index)
Returns the element at the specified position in this list.
=> 리스트의 특정 위치의 성분을 반환한다.
E getFirst()
Returns the first element in this list.
=> 이 리스트의 첫번째 성분을 반환
E getLast()
Returns the last element in this list.
=> 이 리스트의 마지막 성분을 반환
int indexOf(Object o)
Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
=> 특정 성분의 위치를 반환, 없으면 -1 반환
int lastIndexOf(Object o)
Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
=> 리스트의 특정 성분의 마지막 발생(아마 가장 뒤에 있는걸 반환하는듯)의 인덱스를 반환. 없으면 -1 반환
ListIterator<E> listIterator(int index)
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
boolean offer(E e)
Adds the specified element as the tail (last element) of this list.
boolean offerFirst(E e)
Inserts the specified element at the front of this list.
boolean offerLast(E e)
Inserts the specified element at the end of this list.
E peek()
Retrieves, but does not remove, the head (first element) of this list.
E peekFirst()
Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
E peekLast()
Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
E poll()
Retrieves and removes the head (first element) of this list.
E pollFirst()
Retrieves and removes the first element of this list, or returns null if this list is empty.
E pollLast()
Retrieves and removes the last element of this list, or returns null if this list is empty.
E pop()
Pops an element from the stack represented by this list.
void push(E e)
Pushes an element onto the stack represented by this list.
E remove()
Retrieves and removes the head (first element) of this list.
E remove(int index)
Removes the element at the specified position in this list.
boolean remove(Object o)
Removes the first occurrence of the specified element from this list, if it is present.
E removeFirst()
Removes and returns the first element from this list.
boolean removeFirstOccurrence(Object o)
Removes the first occurrence of the specified element in this list (when traversing the list from head to tail).
E removeLast()
Removes and returns the last element from this list.
boolean removeLastOccurrence(Object o)
Removes the last occurrence of the specified element in this list (when traversing the list from head to tail).
E set(int index, E element)
Replaces the element at the specified position in this list with the specified element.
int size()
Returns the number of elements in this list.
Object[] toArray()
Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[] toArray(T[] a)
Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

 

 

후... 정말 많은 것이 있다. 읽어보고 어떤 기능이 있는지 그때마다 보고 사용하면 될 것 같다.

 

다 전부 해석해서 글을 적고 싶었지만... 넘모... 귀찮아... 

LinkedList01.java

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedList01 {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();//타입 미설정 Object로 선언
        LinkedList<Student> members = new LinkedList<Student>();//타입설정

        members.addFirst(new Student("john",10));
        members.addFirst(new Student("kim",11));
        members.add(1, new Student("one position john", 50));
        members.addLast(new Student("last john", 15));

        members.stream().forEach(member -> {
            System.out.println(member.getName());
            System.out.println(member.getAge());
            System.out.println("=====");
        });

        members.remove(1);

        //순회방법 1 : Iterator 사용하기
        Iterator<Student> iterator = members.iterator();//Iterator 선언
        while(iterator.hasNext()){//다음값이 있는지 체크
            System.out.println(iterator.next()); //값 출력
        }

        //순회방법 1 : stream 사용하기
        members.stream().forEach(member -> {
            System.out.println(member.getName());
            System.out.println(member.getAge());
            System.out.println("=====");
        });

        System.out.println(members.size());
    }

    static class Student{
        String name;
        int age;

        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getAge() {
            return age;
        }

        public void setAge(int age) {
            this.age = age;
        }
    }
}

3. ArrayDequeue란?

Deque interface의 사이즈 조정이 가능한 array의 구현체.

Array Deque는 용량 제한이 없다. Thread-safe하지 않다.

외부 동기화의 부제로, 다양한 쓰레드의 동시 접근을 지원하지 않는다.

null은 안된다.

이 클래스는 stack으로 쓸 때 Stack보다는 빠르고 queue로 쓸 때 LinkedList보다 빠르다. 

 

ArrayDeque 생성자 및 메소드 설명 더보기 클릭!

더보기

Constructor and Description

ArrayDeque()
Constructs an empty array deque with an initial capacity sufficient to hold 16 elements.
ArrayDeque(Collection<? extends E> c)
Constructs a deque containing the elements of the specified collection, in the order they are returned by the collection's iterator.
ArrayDeque(int numElements)
Constructs an empty array deque with an initial capacity sufficient to hold the specified number of elements.

 

Modifier and TypeMethod and Description

boolean add(E e)
Inserts the specified element at the end of this deque.
void addFirst(E e)
Inserts the specified element at the front of this deque.
void addLast(E e)
Inserts the specified element at the end of this deque.
void clear()
Removes all of the elements from this deque.
ArrayDeque<E> clone()
Returns a copy of this deque.
boolean contains(Object o)
Returns true if this deque contains the specified element.
Iterator<E> descendingIterator()
Returns an iterator over the elements in this deque in reverse sequential order.
E element()
Retrieves, but does not remove, the head of the queue represented by this deque.
E getFirst()
Retrieves, but does not remove, the first element of this deque.
E getLast()
Retrieves, but does not remove, the last element of this deque.
boolean isEmpty()
Returns true if this deque contains no elements.
Iterator<E> iterator()
Returns an iterator over the elements in this deque.
boolean offer(E e)
Inserts the specified element at the end of this deque.
boolean offerFirst(E e)
Inserts the specified element at the front of this deque.
boolean offerLast(E e)
Inserts the specified element at the end of this deque.
E peek()
Retrieves, but does not remove, the head of the queue represented by this deque, or returns null if this deque is empty.
E peekFirst()
Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
E peekLast()
Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
E poll()
Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
E pollFirst()
Retrieves and removes the first element of this deque, or returns null if this deque is empty.
E pollLast()
Retrieves and removes the last element of this deque, or returns null if this deque is empty.
E pop()
Pops an element from the stack represented by this deque.
void push(E e)
Pushes an element onto the stack represented by this deque.
E remove()
Retrieves and removes the head of the queue represented by this deque.
boolean remove(Object o)
Removes a single instance of the specified element from this deque.
E removeFirst()
Retrieves and removes the first element of this deque.
boolean removeFirstOccurrence(Object o)
Removes the first occurrence of the specified element in this deque (when traversing the deque from head to tail).
E removeLast()
Retrieves and removes the last element of this deque.
boolean removeLastOccurrence(Object o)
Removes the last occurrence of the specified element in this deque (when traversing the deque from head to tail).
int size()
Returns the number of elements in this deque.
Object[] toArray()
Returns an array containing all of the elements in this deque in proper sequence (from first to last element).
<T> T[] toArray(T[] a)
Returns an array containing all of the elements in this deque in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

출처 : https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html

 

여기서 재미있는 것이 ArrayDeque가 Stack보다 빠르고 Queue로 쓸 때는 LinkedList보다 빠르다는 것이다.

 

왜, ArrayDeque가 Stack보다 빠를까? 

 

전에 Stack을 공부할 때 (여기 참고) Stack은 Vector의 기능을 사용한다고 했다.

 

이에 대한 단점 정리하면 다음과 같다. 

  • 모든 메소드에 synchronized가 있기 때문에 단일 스레스 환경에서는 성능이 떨어집니다.
  • Vector 클래스를 상속받았기 때문에 LIFO 구조를 유지하는 것이 아니라 중간에서 데이터를 삭제하고 삽입하는 것이 가능합니다.
  • Stack 클래스를 만들 때 초기 용량을 설정할 수 없습니다.

출처 : https://devlog-wjdrbs96.tistory.com/245

 

하지만 위와 같은 문제를 ArrayDeque를 사용하면 해결된단다. 물론 쓰레드 safe하게 설계도 가능하다.

public class DequeBasedSynchronizedStack<T> {

    // Internal Deque which gets decorated for synchronization.
    private ArrayDeque<T> dequeStore;

    public DequeBasedSynchronizedStack(int initialCapacity) {
        this.dequeStore = new ArrayDeque<>(initialCapacity);
    }

    public DequeBasedSynchronizedStack() {
        dequeStore = new ArrayDeque<>();
    }

    public synchronized T pop() {
        return this.dequeStore.pop();
    }

    public synchronized void push(T element) {
        this.dequeStore.push(element);
    }

    public synchronized T peek() {
        return this.dequeStore.peek();
    }

    public synchronized int size() {
        return this.dequeStore.size();
    }
}

 

출처 : https://www.baeldung.com/java-lifo-thread-safe

4. LinkedList vs ArrayDeque

장점은 내가 이해하기에 다음과 같다. 

1. ArrayDeque는 Array에 의해 지원되고 Array는 LinkList보다 cache-locality 친화적이다. 

2. ArrayDeque는 다음 노드에 추가적인 reference를 유지할 필요가 없기 때문에 LinkedList보다 메모리 효율적이다. 

그래서 ArrayDeque를 queue로 사용할 때 LinkedList대신에 사용함.

5. ArrayList vs ArrayDeque vs LinkedList: which one is best?

그래서 결론적으로 어떤걸 써야하는거야?

 

ArrayList? ArrayDeque? LinkedList? 셋 다 기능도 비슷한데 말이다.

 

이미 이에 대한 내용을 선배 개발자께서 정리했다.

 

출처 : https://qccs.me/classes/cs313/fried/website/list_comparison.html

 

  • 인덱스로 데이터에 접근하고 끝에 삽입, 삭제만 할 경우에는 ArrayList를 사용하라
  • stack, queue, 혹은 deque로 ArrayDeque를 사용하라
  • 리스트를 순회할때 삽입, 삭제하거나 O(1)인 최악의 경우에 마지막에 삽입시 LinkedList를 사용하라

그 순간 순간 사용시에 다시 어떤 것이 나은지 판단하고 꺼내서 사용하면 될 것 같다.

'programming language > Java' 카테고리의 다른 글

[Java] Comparable, Comparator, 정렬 방법  (0) 2022.04.21
Map 알아보기  (0) 2022.04.13
직렬화란 무엇인가 ? / serialVersionUID 설정 이유  (0) 2022.04.11
Stack, Queue, PriorityQueue  (0) 2022.04.10
List 관련 질문 답변 정리  (3) 2022.04.04

'programming language/Java'의 다른글

  • 현재글Deque, LinkedList 와 ArrayDeque

관련글

티스토리툴바