[자료구조] LinkedList

LinkedList

 Node라고 불리는 각 요소가 데이터와 포인터를 사용하여 한 줄로 연결되는 자료구조.

코드

/* List.java : list ADT */
public interface List<E> extends Iterable<E> {
    void add(E item);
    E get(int index);
    int size();
    void remove(int index);
    boolean isEmpty();
    void clear();
}

/* SinglyLinkedList.java */
import java.util.Iterator;

public class SinglyLinkedList<E> implements List<E> {
    public static class Node<E> {
        private E data;
        private Node<E> nextNode;

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

        public E get() {
            return this.data;
        }

        public void set(E data) {
            this.data = data;
        }

        public void setNext(Node<E> node) {
            this.nextNode = node;
        }

        public Node<E> getNext() {
            return this.nextNode;
        }
    }

    Node<E> head = null;
    Node<E> tail = null;
    int size = 0;

    public SinglyLinkedList() {}

    public void add(E data) {
        Node<E> last = tail;
        Node<E> newNode = new Node<>(data);

        size++;

        tail = newNode;

        if (last == null) {
            this.head = newNode;
        }
        else {
            last.setNext(newNode);
        }
    }

    // should be implement
    // https://inpa.tistory.com/entry/DS-%F0%9F%A7%B1-Singly-LinkedList-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Java%EB%A1%9C-%EC%8B%A4%EC%A0%84-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
    public void add(E data, int index) {
        if (index > this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> prev = this.head;
        Node<E> current = prev.nextNode;

        int i = 0;
        while(i++ < index) {
            prev = prev.nextNode;
            current = prev.nextNode;
        }

        Node<E> node = new Node<>(data);
        current = node;
        prev.nextNode = current;

        this.size++;
    }

    public E get(int index) {
        Node<E> current = this.head;

        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }

        return current.get();
    }

    private Node<E> searchNode(int index) {
        Node<E> current = this.head;

        for (int i = 0; i < index; i++) {
            current = current.getNext();
        }

        return current;
    }

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

    public void removeFirst() {
        if (head == null) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> first = head.getNext();

        head.setNext(null);
        head.set(null);

        head = first;

        if (head == null) {
            tail = null;
        }
        this.size--;
    }

    public void remove(int index) {
        if (index > this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        if (index == 0) {
            this.removeFirst();
        }

        Node<E> prev = searchNode(index - 1);
        Node<E> del = prev.getNext();
        Node<E> next = del.getNext();

        prev.setNext(next);

        size--;
    }

    public boolean isEmpty() {
        return this.head.nextNode == null && this.head == null;
    }

    public void clear() {
        this.head = null;
        this.size = 0;
    }

    public Iterator<E> iterator() {
        return new SinglyLinkedListIterator<>(this);
    }

    // Iterator
    class SinglyLinkedListIterator<E> implements Iterator<E> {
        SinglyLinkedList<E> list;
        int index = 0;

        public SinglyLinkedListIterator(SinglyLinkedList<E> list) {
            this.list = list;
        }

        public boolean hasNext() {
            return index < list.size();
        }

        public E next() {
            return list.get(index++);
        }
    }
}

class Test {
    public static void main(String[] args) {
        SinglyLinkedList<String> list = new SinglyLinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

        for(String e : list) {
            System.out.println(e);
        }
        System.out.println("");

        list.removeFirst(); 
        for(String e : list) {
            System.out.println(e);
        }
        System.out.println("");

        list.remove(1);
        for(String e : list) {
            System.out.println(e);
        }
        System.out.println("");

        list.forEach(System.out::println);
    }
}

 

실행 결과

A
B
C
D

B
C
D

B
D

B
D

 

 

2024.09.02 - [Java] - [Java] 14. Collections Framework

[Java] 14. Collections Framework

 

---

 

 

출처: https://github.com/gikpreet/class-programming_with_java/tree/master

GitHub - gikpreet/class-programming_with_java