데이터 구조 (2) - 링크

애매모호 한 뒷 잠 을 채우다
링크
링크 는 데이터 집합 을 저장 하 는 데이터 구조 로 그 는 가장 간단 한 동적 데이터 구조 이다.지난 편 에서 우 리 는 분명히 간단 한 동적 배열 을 실현 했다.이것 은 단지 사용 자 를 대상 으로 하 는 것 일 뿐 입 니 다. 사실은 배열 의 밑바닥 은 정적 인 배열 입 니 다. 우 리 는 간단하게 복사 한 그 당시 에 용량 의 증 가 를 실 현 했 을 뿐 입 니 다. 하지만!!링크 는 진정한 의미 의 동적 데이터 구조 이다.
링크 의 장점

진정한 동적 데이터 구 조 는 고정 용량 의 문 제 를 처리 할 필요 가 없다

상수 시간 내 에 용량 을 확장 할 수 있다

링크 의 단점

무 작위 방문 효율 이 낮다

링크 에서 포인터 인용 을 유지 하고 메모리 낭비

링크 와 배열 의 간단 한 대비

배열 은 의미 있 는 색인 에 가장 사용 되 는데 그 가장 큰 특징 은 빠 른 조회 와 수정 을 지원 하 는 것 이다

.

링크 는 색인 이 의미 가 있 는 상황 에 적용 되 지 않 고 가장 큰 특징 은 동태 이 며 데 이 터 를 빨리 읽 고 삽입 하고 삭제 할 수 있다

.
자신의 링크 클래스 를 실현 하 다.
마찬가지 로 우 리 는 이전 배열 의 소개 에서 우 리 는 자신의 링크 를 완성 하고 가장 간단 한 추가 삭제 기능 을 지원 합 니 다.

public class LinkedList {

    private class Node{
        private E e;
        private 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;
    }

    /**
     *           
     * @param index
     * @param e
     */
    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        //       ，                 
        Node prve = dummyHead;

        for (int i = 0; i < index; i++) {
            //              
            prve = prve.next;
        }
        prve.next = new Node(e,prve.next);
        size++;
    }

    /**
     *      
     */
    public void addFirst(E e){
//        Node node = new Node(e);
//        node.next = dummyHead;
//        dummyHead = node;

        dummyHead = new Node(e,dummyHead);
    }

    /**
     *         
     * @param e
     */
    public void addLast(E e){
        this.add(size,e);
    }

    public E get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

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

        return cur.e;
    }

    //          
    public E getFirst(){
        //                    
        return dummyHead.next.e;
    }

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

    //            
    public void set(int index ,E e){
        //   get    ，     ，      
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node cur = dummyHead.next;
        for (int i = 0; i < size; 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;
    }

    //         
    public void remove(int index){
        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 ;
        }
        //      
        Node retNode = prev.next;
        //         
        prev.next = retNode.next;
        //     
        retNode.next = null;
        size --;
    }

    //           
    public void removeFirst(){
        //               
        dummyHead.next = dummyHead.next.next;
        size--;
    }

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

    @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();
    }
}

링크 에서 가상 헤드 노드 의 역할
첫 번 째 요소 (진 두 노드) 는 앞 순서 노드 가 없 기 때문이다.우리 가 조작 을 할 때 모두 머리 노드 에 대해 단독 적 인 판단 을 해 야 한다. 그러면 진짜 머리 노드 의 논 리 는 시간 이 있다.그래서 편 의 를 위해 우 리 는 가상 헤드 노드 를 설정 하여 진짜 헤드 노드 의 특수성 을 차단 합 니 다.
단순 복잡 도 분석
우 리 는 링크 의 조작 에서 쉽게 알 수 있 듯 이 삭제 와 수정 에 대해 이 몇 가지 조작 의 복잡 도 는 모두 O (n) 이다. 그러나 만약 에 우리 가 링크 의 머리 를 증가/삭제/검사 하 는 조작 만 한다 면 그의 복잡 도 는 바로 O (1) 이다. 여기 서도 우리 의 링크 가 하기에 적합 한 일 을 알 수 있다.