[Java Study] - LinkedList , Queue in Collection framework

LinkedList는  java Collection framework에서 List 인터페이스를 구현한 클래스로 List 인터페이스로 사용 가능한 컬렉션입니다.

 

출처 : https://howtodoinjava.com/java/collections/java-linkedlist-class/

 

 

LinkedList에는 Node로 불리는 요소가 있는데요 

 

요소는 데이터와 다음 Node의 주소값 2가지로 나눌 수 있습니다.

 

• Head 는 오직 리스트의 첫번째 요소 주소값 만 가지고 있습니다.
• 리스트의 마지막 요소는 노드의 주소 값 부분이 null 입니다.

 

이렇게 이전요소와 다음요소가 직접적으로 연결된 데이터 구조를 linear data strucure(선형 자료구조) 라고 합니다.

LinkedList 는 대표적인 선형 자료구조 중 하나입니다.

 

위의 예시는 타입을 Integer 으로 지정 했을 때이다.

데이터 값은 모두 Integer

 

 

메서드

 

LinkedList 에서 메서드 중 일부를 살펴보면

• boolean add(Object o ) : 리스트의 마지막 부터 해당 요소를 추가한다.
• void add(int index , Object element) : 지정한 index 위치에 요소를 추가한다.
• void addFirst(Objct o) : 리스트의 첫번째에 해당 요소를 추가한다.
• void addLast(Object o) : 리스트의 제일 마지막에 요소를 추가한다.
• int size() : 리스트에 들어 있는 요소 개수를 반환 한다.
• boolean contains(Object o) : 리스트에 해당 요소가 있으면 true , 그렇지 않으면 false 를 반환한다.
• boolean remove(Object o) : 리스트에 해당 요소를 삭제한다.
• int indexOf(Object o) : 해당 요소가 리스트의 몇 번째 인덱스에 있는지 반환한다. 만약 없으면 -1을 반환한다.

 

※ add(Object o) , addLast(Object o) 메서드의 차이점은 무엇일 까?

두 메서드는 동일한 기능을 수행하는데 ,

차이점은 add(Object o) 는 수행이 잘 되었는지 boolean 값을 반환하고,

addLast(Object o)는 아무 값도 반환하지 않는다.

 

또 하나는,

add(Object o) 는 Collection 인터페이스 안에 선언되어 있기 때문에 , 

List 인터페이스를 구현한 클래스 와 Queue 인터페이스를 구현한 클래스에서 전부 사용 할 수 지만

 

addLast(Object o) 는 Deque interface 안에 선언되어 있기 때문에 

Deque interface를 구현한 클래스만 사용할 수 있다.

 

즉 사용 범위가 다른 것이다.

 

reference 

https://www.codekru.com/java/linked-list-addfirst-and-addlast-methods

 

 

구현 해보기

#1

 

 

 

 

#2 

 

 

public class ListNode<E> {
    private int size;
    private Node head;

    class Node {
        E data;
        Node next;

        public Node(E data) {
            this.data = data;
            this.next = null;
        }

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }

    }

    public ListNode() {
        head = null;
        size = 0;
    }

    boolean add(E data) {
        // list가 비어 있으면 head node 에 첫 번째 node 값을 할당한다.
        if (head == null) {
            head = new Node(data);
        } else { // list에 값이 있다면
            Node node = head; // 리스트 연결을 위한 임시 노드
            while (node.next != null) { // 리스트의 마지막 까지 반복
                node = node.next;
            }
            node.next = new Node(data);
        }
        size++;
        return true;
    }

    void add(int index, E data) {
        if (index == 0) {
            head = new Node(data, head);
        } else {
            Node node = getNode(index-1);
            node.next = new Node(data , node.next);
        }
        size++;
    }

    Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
}

 

  public static void main(String[] args) {
       	ListNode listNode = new ListNode();
        listNode.add(11);
        listNode.add(22);
        listNode.add(33);
    }

 

 

 

 

Queue

Queue 인터페이스는 FIFO(First-In First-Out) 자료구조에서 사용되는 메서드를 정의하고 있다.

 

 

위에서 살펴본 LinkedList가 Queue 인터페이스를 구현한 대표적인 클래스다.

 

메서드	설명
boolean add(E e)	queue 에 해당 원소를 넣는다.  성공하면 true를 리턴하고 실패 하면  예외가 발생한다.
boolean offer(E e)	queue 에 해당 원소를 넣는다. 성공하면 true를 리턴하고 실패 하면 false 를 리턴한다.
E element()	queue 의 head를 리턴한다.  만약 queue가 비어 있다면 예외가 발생한다.
E peek()	queue 의 head를 리턴한다.  만약 queue가 비어 있다면 null 을 리턴한다.
E remove()	queue 의 head를 리턴하고 , queue에서 제거한다. 만약 queue가 비어 있다면 예외가 발생한다.
E poll()	queue 의 head를 리턴하고, queue에서 제거한다. 만약 queue가 비어 있다면 null을 리턴한다.
boolean isEmpty()	queue 가 비어있는지 확인 한다.  비어있으면 true , 데이터가 있으면 false 를 리턴 한다.

 

public class Example {
    public static void main(String[] args) {
        // 정수 값 담는 queue 생성
        Queue<Integer> queue = new LinkedList<>();
        queue.add(10); // 정수 10을 queue 에 넣는다.
        queue.add(20); // 정수 20을 queue 에 넣는다
        queue.add(30); // 정수 30을 queue 에 넣는다.
        queue.add(40);
        queue.add(50);
        queue.add(60);
        queue.add(70);
        System.out.println(queue.element()); // 10 을 반환
        System.out.println(queue.peek()); // 10을 반환
        System.out.println(queue.remove()); // 10울 반환하고  10을 queue 에서 제거한다.
        System.out.println(queue.peek()); //위에서 10을 제거 했기 때문에 20을 반환
        System.out.println(queue.poll()); // 20을 반환하고 20을 queue 에서 제거한다.
        System.out.println(queue.isEmpty()); // queue에 data 가 있으므로 false;
    }
}

 

예외가 발생하는 경우 - element() , remove()

public class Example {
    public static void main(String[] args) {
        // 정수 값 담는 queue 생성
        Queue<Integer> queue = new LinkedList<>();
        System.out.println(queue.element()); // java.util.NoSuchElementException 발생
    }
}

NoSuchElementException 발생 (Runtime Exception)

public class NoSuchElementException extends RuntimeException {
    private static final long serialVersionUID = 6769829250639411880L;

    /**
     * Constructs a {@code NoSuchElementException} with {@code null}
     * as its error message string.
     */
    public NoSuchElementException() {
        super();
    }

    /**
     * Constructs a {@code NoSuchElementException}, saving a reference
     * to the error message string {@code s} for later retrieval by the
     * {@code getMessage} method.
     *
     * @param   s   the detail message.
     */
    public NoSuchElementException(String s) {
        super(s);
    }
}

public class Example {
    public static void main(String[] args) {
        // 정수 값 담는 queue 생성
        Queue<Integer> queue = new LinkedList<>();
        System.out.println(queue.remove()); //java.util.NoSuchElementException 발생
    }
}

 

null 을 반환하는 경우 - peek() , poll()

public class Example {
    public static void main(String[] args) {
        // 정수 값 담는 queue 생성
        Queue<Integer> queue = new LinkedList<>();
        System.out.println(queue.peek()); // null 반환
    }
}

public class Example {
    public static void main(String[] args) {
        // 정수 값 담는 queue 생성
        Queue<Integer> queue = new LinkedList<>();
        System.out.println(queue.poll()); // null 반환
    }
}

 

 

양방향 queue 에 해당하는 LinkedList

위에서 살펴본 queue 는 FIFO 자료구조로 데이터를 넣고 제거하는 것이 한쪽으로만 가능했다. (단 방향)

이에 비해 LinkedList 는 양방향으로 데이터를 넣고 제거하는 것이 가능하다.

그림으로 살펴보면

 

위에서 살펴본 queue 메서드를 포함하여 LinkedList 클래스에 추가 된 것이

메서드	설명
addFirst()	queue 의 시작 지점에  해당 요소를 넣는다.
addLast()	queue 의 끝 지점에 해당 요소를 넣는다.
peekFirst()	queue 의 시작 지점에 있는 해당 요소를 리턴한다.
peekLast()	queue 의 끝 지점에  해당 요소를 리턴한다.
pollFirst()	queue 의 시작 지점에 있는 해당 요소를 리턴하고 , 요소를 삭제한다.
pollLast()	queue 의 끝 지점에 있는 해당 요소를 리턴하고 , 요소를 삭제한다.

 

이다. 

public class Example {
    public static void main(String[] args) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        queue.addFirst(40); // LinkedList 시작점에 원소를 추가
        queue.add(50);
        System.out.println(queue); // [40 , 10 , 20 ,30 ,50]
        System.out.println(queue.peekLast()); // 50
        System.out.println(queue.peekFirst()); // 40
    }
}

 

 

public class Example {
    public static void main(String[] args) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(10);
        queue.add(20);
        queue.add(30);
        queue.addFirst(40); // LinkedList 시작점에 원소를 추가
        queue.add(50);
        System.out.println(queue); // [40 , 10 , 20 ,30 ,50]
        System.out.println(queue.pollFirst()); // 40을 리턴하고 queue 에서 40을 제거
        System.out.println(queue); // [10, 20, 30, 50]
        System.out.println(queue.pollLast()); // 50을 리턴하고 queue 에서 50을 제거
        System.out.println(queue); // [10, 20, 30]
    }
}

 

 

 

 

 

 

 

REFERENCE

https://www.geeksforgeeks.org/linked-list-set-1-introduction/
https://beginnersbook.com/2013/12/linkedlist-in-java-with-example/
https://www.upgrad.com/blog/what-is-linear-data-structure/
https://www.programiz.com/java-programming/queue
이것이 자바다