[Java-자료구조] LinkedList 사용과 구현

LinkedList

• List 인터페이스를 상속받은 클래스
• 연속적인 공간을 사용하지 않고 모든 데이터가 노드(데이터 + 주소)로 구성되어있다.
• index가 없기 때문에 임의접근이 불가능하다.
• Singly LinkedList(data + nextNode주소) , Doubly LinkedList(prevNode주소 + data + nextNode주소)
• 자바에서는 LinkedList는 Doubly LinkedList로 구현되어 있다.
• 데이터의 순서가 있으며 동일 데이터에 대한 중복 저장을 허용한다.

LinkedList

멤버변수: size(들어있는 element 개수), head(시작 node주소), tail(마지막 node주소)

 

LinkedList 사용법

import java.util.LinkedList;

자바는 java.util.LinkedList Class를 통해 LinkedList를 제공하고 있다.

 

LinkedList 선언

LinkedList ll = new LinkedList(); // 타입 미설정(Object)로 가능하나 보통 type을 설정해줌
LinkedList<Integer> ex1 = new ArrayList<>(); // Wrapper Class로 LinkedList 생성
LinkedList<Integer> ex2 = new ArrayList<>(Arrays.asList(1,2,3)); // 직접 element를 넣어줌.

다양한 방식으로 LinkedList의 생성이 가능하다.

 

LinkedList 메서드

데이터 추가

linkedList.add(Object element); // 맨 뒤에 element 추가
linkedList.add(int index, Object element); // 특정 index위치에 element 추가
linkedList.addFirst(Object element); // 0번째 위치에 element 추가
linkedList.addLast(Object element); // 맨 뒤에 element 추가

데이터 삭제

linkedList.remove(); // head에 위치한 element를 제거
linkedList.remove(int index); // 특정 index에 있는 node 제거
linkedList.remove(Object element); // 특정 element를 제거
linkedList.removeFirst(); //첫 번째 node를 제거
linkedList.removeLast(); // 마지막 node를 제거
linkedList.clear(); // LinkedList 내부에 있는 모든 element 제거

데이터 수정

linkedList.set(int index, Object element); // 특정 index에 있는 data를 새로운 data로 변경

데이터 검색

linkedList.contains(Object element); // 특정 element의 존재 여부 확인
linkedList.indexOf(Object element); // 특정 element의 index 반환
linkedList.get(int index); // 특정 index에 잇는 element 반환
linkedList.getFirst(); // 첫번째 element 반환
linkedList.getLast(); // 마지막 element 반환

misc

linkedList.size(); //element의 개수 반환
linkedList.toArray(); // array로 변경해서 반환
linkedList.toArray(Object[] a); // runtime에서의 type을 반영하여 array로 변환하여 반환
linkedlist.clone(); // 현재 linkedlist에 대해 shallow copy 반환

---

LinkedList 장단점

장점

• 자료의 삽입과 삭제가 용이
• 리스트 내의 자료의 이동 필요없음
• 연속적인 할당이 필요없기 때문에 크기의 지정이 필요없음

단점

• 포인터로 인한 저장공간의 낭비
• 순차탐색을 해야하기 때문에 탐색시간이 많이 소요

---

구현

List 인터페이스

/**
 * 자바 List Interface<br>
 * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현합니다.
 *
 * @param <E> the type of elements in this list
 */

public interface List<E> {
    /**
     * 리스트에 요소를 추가
     *
     * @param element 리스트에 추가할 요소
     * @return  리스트에서 중복을 허용하지 않은 경우 리스트에 이미 중복되는
     *          요소가 있는 경우 {@code false}를 반환하고, 중복되는 원소가
     *          없을 경우 {@code true}를 반환
     */
    boolean add(E element);

    /**
     * 리스트에 요소를 특정 위치에 추가합니다.
     * 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀립니다.
     *
     * @param index  리스트에 추가할 특정 위치
     * @param element 리스트에 추가할 요소
     */
    void add(int index, E element);

    /**
     * 리스트의 index 위치의 요소를 제거합니다.
     *
     * @param index 리스트에서 삭제할 요소의 위치
     * @return 삭제한 요소를 반환
     */
    E remove(int index);

    /**
     * 리스트에서 특정 요소를 삭제합니다.
     * 여러 개일 경우 가장 처음 발견한 요소만 삭제됩니다.
     *
     * @param element 리스트에서 삭제할 요소
     * @return 리스트에서 삭제할 요소가 없거나 삭제 실패시 {@return false}
     *         삭제에 성공할 경우 {@return true}
     */
    boolean remove(Object element);

    /**
     * 리스트에서 index 위치의 요소를 반환합니다.
     *
     * @param index 리스트에서 접근할 위치
     * @return 해당 index의 요소
     */
    E get(int index);

    /**
     * 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
     *
     * @param index 값을 수정할 위치
     * @param element 새로 대체할 값
     */
    void set(int index, E element);

    /**
     * 특정 요소가 리스트에 있는지 확인합니다
     *
     * @param element
     * @return 리스트에 특정 요소가 존재하는 경우 {@code true}
     *          존재하지 않는 경우 {@code false}
     */
    boolean contains(Object element);

    /**
     * 리스트에 특정 요소가 위치한 위치를 반환합니다
     *
     * @param element
     * @return 리스트에 처음으로 element와 일치하는 index를 반환하고 없다면 -1를 반환
     *
     */
    int indexOf(Object element);

    /**
     * 리스트에 들어있는 요소의 개수를 반환합니다.
     *
     * @return 리스트에 들어있는 요소의 수 를 반환
     */
    int size();

    /**
     * 리스트가 비어있는지 여부를 반환합니다
     *
     * @return 리스트에 요소가 없는 경우 {@code false} 요소가 있는 경우 {@code true}
     */
    boolean isEmpty();

    /**
     * 리스트를 비웁니다.
     */
    public void clear();
}

 

1. Singly LinkedList

public class Node<T> {
    private T data;
    private Node<T> next;

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

    T getData(){
        return this.data;
    }

    void setData(T data){
        this.data = data;
    }

    Node<T> getNext(){
        return next;
    }

    void setNext(Node<T> next){
        this.next = next;
    }
}

import java.lang.reflect.Array;
import java.util.NoSuchElementException;

public class SinglyLinkedList<T> implements List<T> {

    private Node<T> head;
    private Node<T> tail;
    private int size;

    SinglyLinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    private Node<T> search(int index){
        if(index<0 || index >=size){
            throw new IndexOutOfBoundsException();
        }
        Node<T> tmp = head;
        for(int i=0;i<index;i++){
            tmp = tmp.getNext();
        }
        return tmp;
    }

    public void addFirst(T element) {

        Node<T> newNode = new Node<T>(element);
        newNode.setNext(head);
        head = newNode;
        size++;
        if(head.getNext() == null){
            tail = head;
        }
    }

    public void addLast(T element){
        Node<T> newNode = new Node<T>(element);
        if(size == 0){
            addFirst(element);
            return;
        }
        tail.setNext(newNode);
        tail = newNode;
        size++;
    }

    @Override
    public boolean add(T element) {
        addLast(element);
        return true;
    }

    @Override
    public void add(int index, T element) {
        if(index<0 || index > size){
            throw new IndexOutOfBoundsException();
        }
        if(index==0){
            addFirst(element);
            return;
        }
        if(index==size){
            addLast(element);
            return;
        }
        Node<T> newNode = new Node<T>(element);
        Node<T> prevNode = search(index-1);
        Node<T> nextNode = prevNode.getNext();

        prevNode.setNext(null);
        prevNode.setNext(newNode);
        newNode.setNext(nextNode);
        size++;
    }

    public T remove(){
        Node<T> headNode = head;
        if(headNode == null){
            throw new NoSuchElementException();
        }
        T element = headNode.getData();
        Node<T> nextNode = head.getNext();
        head.setData(null);
        head.setNext(null);
        head = nextNode;
        size--;

        if(size==0){
            tail = null;
        }
        return element;
    }

    @Override
    public T remove(int index) {
        if(index == 0){
            return remove();
        }
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> prevNode = search(index - 1);
        Node<T> targetNode = prevNode.getNext();
        Node<T> nextNode = targetNode.getNext();
        T data = nextNode.getData();

        prevNode.setNext(nextNode);
        targetNode.setNext(null);
        targetNode.setData(null);
        size--;
        return data;
    }

    @Override
    public boolean remove(Object element) {
        Node<T> prevNode = head;
        Node<T> tmp = head;

        for(;tmp!=null;tmp=tmp.getNext()){
            if(element.equals(tmp.getData())){
                break;
            }
            prevNode = tmp;
        }

        if(tmp == null){
            return false;
        }

        if(tmp.equals(head)){
            remove();
        }else{
            prevNode.setNext(tmp.getNext());
            tmp.setData(null);
            tmp.setNext(null);
            size--;
        }
        return true;
    }

    @Override
    public T get(int index) {
        Node<T> targetNode = search(index);
        return targetNode.getData();
    }

    @Override
    public void set(int index, T element) {
        Node<T> targetNode = search(index);
        targetNode.setData(null);
        targetNode.setData(element);
    }

    @Override
    public boolean contains(Object element) {
        return indexOf(element)>=0;
    }

    @Override
    public int indexOf(Object element) {
        int index = 0;
        for(Node<T> i=head; i!=null; i=i.getNext()){
            if(element.equals(i.getData())){
                return index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void clear() {
        for(Node<T> i=head;i!=null;){
            Node<T> nextNode = i.getNext();
            i.setData(null);
            i.setNext(null);
            i = nextNode.getNext();
        }
        head = null;
        tail = null;
        size = 0;
    }

    public Object clone() throws CloneNotSupportedException{
        SinglyLinkedList<? super T> clone = (SinglyLinkedList<? super T>) super.clone();
        clone.head = null;
        clone.tail = null;
        clone.size =0;

        for(Node<T> i = head; i!=null;i = i.getNext()){
            clone.addLast(i.getData());
        }
        return clone;
    }

    public Object[] toArray(){
        Object[] array = new Object[size];
        int idx = 0;
        for(Node<T> i = head; i != null; i = i.getNext()){
            array[idx++] = (T) i.getData();
        }
        return array;
    }

    public <E> E[] toArray(E[] a){
        if(a.length<size){
            a = (E[]) Array.newInstance(a.getClass().getComponentType(),size);
        }
        int i=0;
        Object[] result = a;
        for(Node<T> j = head; j!=null; j=j.getNext()){
            result[i++] = j.getData();
        }
        return a;
    }
}

 

2.Doubly LinkedList

public class DoublyLinkedListNode<T> {

    private T data;
    private DoublyLinkedListNode<T> prev;
    private DoublyLinkedListNode<T> next;

    DoublyLinkedListNode(T data){
        this.data = data;
        prev = null;
        next = null;
    }

    T getData(){
        return data;
    }

    void setData(T data){
        this.data = data;
    }

    DoublyLinkedListNode<T> getPrev(){
        return prev;
    }

    void setPrev(DoublyLinkedListNode<T> prev){
        this.prev = prev;
    }

    DoublyLinkedListNode<T> getNext(){
        return next;
    }

    void setNext(DoublyLinkedListNode<T> next){
        this.next = next;
    }
}

import java.lang.reflect.Array;
import java.util.NoSuchElementException;

public class DoublyLinkedList<T> implements List<T>, Cloneable {

    protected DoublyLinkedListNode<T> head;
    protected DoublyLinkedListNode<T> tail;
    protected int size;

    DoublyLinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    private DoublyLinkedListNode<T> search(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        DoublyLinkedListNode<T> tmp = head;
        for(int i=0; i<index; i++){
            tmp = tmp.getNext();
        }
        return tmp;
    }

    public void addFirst(T element){
        DoublyLinkedListNode<T> tmp = head;
        head = new DoublyLinkedListNode<>(element);
        if(tmp == null){
            tail = head;
            size++;
            return;
        }
        tmp.setPrev(head);
        head.setNext(tmp);
        size++;
    }

    public void addLast(T element){
        if(size == 0){
            addFirst(element);
            return;
        }
        DoublyLinkedListNode<T> tmp = tail;
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(element);
        tail = newNode;
        tmp.setNext(tail);
        tail.setPrev(tmp);
        size++;
    }

    @Override
    public boolean add(T element) {
        addLast(element);
        return true;
    }


    @Override
    public void add(int index, T element) {
        if(index<0 || index > size){
            throw new IndexOutOfBoundsException();
        }
        if(index==0){
            addFirst(element);
            return;
        }
        if(index==size){
            addLast(element);
            return;
        }
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(element);
        DoublyLinkedListNode<T> prevNode = search(index-1);
        DoublyLinkedListNode<T> nextNode = prevNode.getNext();

        prevNode.setNext(newNode);
        newNode.setPrev(prevNode);
        newNode.setNext(nextNode);
        nextNode.setPrev(newNode);
        size++;
    }

    public T removeFirst(){
        DoublyLinkedListNode<T> headNode = head;
        if(headNode == null){
            throw new NoSuchElementException();
        }
        T element = headNode.getData();
        DoublyLinkedListNode<T> nextNode = head.getNext();
        head.setData(null);
        head.setNext(null);
        head = nextNode;
        size--;

        if(size==0){
            tail = null;
        }
        return element;
    }

    public T removeLast(){
        if(size==1) {
            return removeFirst();
        }
        DoublyLinkedListNode<T> prevNode = tail.getPrev();
        T element = tail.getData();
        tail.setNext(null);
        tail.setPrev(null);
        tail.setData(null);
        tail = prevNode;
        size--;
        if(size==0){
            tail = null;
        }
        return element;
    }

    public T remove(){
        return removeFirst();
    }

    @Override
    public T remove(int index) {
        if(index == 0){
            return removeFirst();
        }
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        DoublyLinkedListNode<T> prevNode = search(index-1);
        DoublyLinkedListNode<T> targetNode = prevNode.getNext();
        DoublyLinkedListNode<T> nextNode = targetNode.getNext();
        T data = targetNode.getData();

        prevNode.setNext(nextNode);
        nextNode.setPrev(prevNode);
        targetNode.setData(null);
        targetNode.setNext(null);
        targetNode.setPrev(null);
        size--;
        return data;
    }

    @Override
    public boolean remove(Object element) {
        DoublyLinkedListNode<T> prevNode = head;
        DoublyLinkedListNode<T> tmp = head;

        for(;tmp != null; tmp = tmp.getNext()){
            if(element.equals(tmp.getData())){
                break;
            }
            prevNode = tmp;
        }

        if(tmp == null){
            return false;
        }

        if(tmp.equals(head)){
            remove();
        }else{
            prevNode.setNext(tmp.getNext());
            tmp.getNext().setPrev(prevNode);
            tmp.setData(null);
            tmp.setNext(null);
            size--;
        }
        return false;
    }

    public T getFirst(){
        return head != null ? head.getData() : null;
    }

    public T getLast(){
        return tail != null ? tail.getData() : null;
    }

    @Override
    public T get(int index) {
        DoublyLinkedListNode<T> targetNode = search(index);
        return targetNode.getData();
    }

    @Override
    public void set(int index, T element) {
        DoublyLinkedListNode<T> targetNode = search(index);
        targetNode.setData(element);
    }

    @Override
    public boolean contains(Object element) {
        return indexOf(element)>=0;
    }

    @Override
    public int indexOf(Object element) {
        int index = 0;
        for(DoublyLinkedListNode<T> i = head; i!=null;i=i.getNext()){
            if(element.equals(i.getData())){
                return index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void clear() {
        for(DoublyLinkedListNode<T> i = head; i!= null;){
            DoublyLinkedListNode<T> nextNode = i.getNext();
            i.setData(null);
            i.setNext(null);
            i.setPrev(null);
            i = nextNode;
        }
        head = null;
        tail = null;
        size = 0;
    }

    public Object clone() throws CloneNotSupportedException {
        DoublyLinkedList<? super T> clone = (DoublyLinkedList<? super T>) super.clone();
        clone.head = null;
        clone.tail = null;
        clone.size = 0;

        for(DoublyLinkedListNode<T> i = head; i != null; i = i.getNext()){
            if(i.getData()!=null){
                clone.add(i.getData());
            }
        }
        return clone;
    }

    public Object[] toArray(){
        Object[] array = new Object[size];
        int index = 0;
        for(DoublyLinkedListNode<T> i = head; i!=null;i=i.getNext()){
            array[index++] = (T) i.getData();
        }
        return array;
    }

    public <E> E[] toArray(E[] array){
        if(array.length<size) {
            array = (E[]) Array.newInstance(array.getClass().getComponentType(), size);
        }
            int index = 0;
            Object[] result = array;
            for(DoublyLinkedListNode<T> j=head; j!=null; j=j.getNext()){
                result[index++] = j.getData();
            }
            return array;
    }
}