데이터 구조의 링크 의 실현

글 목록

소개
실현

1. 프로필
4. 567917. 동적 배열, 스 택 과 대열 의 바 텀 은 모두 정적 배열 에 의존 하고 resize 로 고정 용량 문 제 를 해결한다.그리고 링크 는 진정한 동적 데이터 구조 이다
2. 실현

public class LinkedList<E> {
     

    private class Node{
     
        public E e;
        public Node next;

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

        public Node(E e){
     
            this(e, null);
        }

        public Node(){
     
            this(null, null);
        }

        @Override
        public String toString(){
     
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedList(){
     
        dummyHead = new Node();
        size = 0;
    }

    //           
    public int getSize(){
     
        return size;
    }

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

    //     index(0-based)        e
    //              ，   ：）
    public void add(int index, E e){
     

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        size ++;
    }

    //           e
    public void addFirst(E e){
     
        add(0, e);
    }

    //            e
    public void addLast(E e){
     
        add(size, e);
    }

    //       index(0-based)      
    //              ，   ：）
    public E get(int index){
     

        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        return cur.e;
    }

    //           
    public E getFirst(){
     
        return get(0);
    }

    //            
    public E getLast(){
     
        return get(size - 1);
    }

    //       index(0-based)       e
    //              ，   ：）
    public void set(int index, E e){
     
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        cur.e = e;
    }

    //           e
    public boolean contains(E e){
     
        Node cur = dummyHead.next;
        while(cur != null){
     
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    //       index(0-based)     ,        
    //              ，   ：）
    public E remove(int index){
     
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;

        return retNode.e;
    }

    //            ,        
    public E removeFirst(){
     
        return remove(0);
    }

    //             ,        
    public E removeLast(){
     
        return remove(size - 1);
    }

    //         e
    public void removeElement(E e){
     

        Node prev = dummyHead;
        while(prev.next != null){
     
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }

        if(prev.next != null){
     
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }

    @Override
    public String toString(){
     
        StringBuilder res = new StringBuilder();

        Node cur = dummyHead.next;
        while(cur != null){
     
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }
}