자바 데이터 구조 기초:단일,양 방향 링크

단 방향 링크
단 방향 링크 는 순서 구조의 선형 표 보다 가장 큰 장점 은 저장 위 치 를 확보 하지 않 고 포인터 로 다음 요 소 를 가리 키 기만 하면 된다 는 것 이다.
싱글 체인 다이어그램

그림 이 비교적 거 칠 어서 간단하게 설명해 주세요.
위의 네 개의 장방형 은 모든 장방형 이 하나의 노드 이다.장방형 에서 하 나 는 두 가지 물건 을 포함 하고 하 나 는 현재 노드 의 요소 이 며 하 나 는 다음 노드 를 가리 키 는 주소 이다.이 다음 노드 의 주 소 는 다음 노드 의 요 소 를 가리킨다.이런 식 으로 유추 하 다.
가장 왼쪽 에 있 는 것 을 머리 노드 라 고 하 는데 똑 같이 맨 뒤의 것 을 꼬리 노드 라 고 한다.
그래서 우리 의 모든 조작 은 노드 에 따라 조작 된다.
코드
이 코드 들 은 모두 매우 상세 한 주석 이 있 기 때문에 나 는 너무 많은 설명 을 하지 않 을 것 이다.너 는 직접 로 컬 아이디어 에서 한 번 실행 하면 모두 알 게 될 것 이다.

package com.zxy.lianbiao;
/**
 * @Author Zxy
 * @Date 2021/2/3 21:25
 * @Version 1.0
 */
/**
 *              
 *
 * @param <E>
 */
public class MySinglyLinkedList<E> implements MyList<E> {
    /**
     *             
     */
    class Node<E> {
        private E item; //     
        private Node next; //          
        public Node(E item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    private Node head; //          
    private int size; //        
    /**
     *         
     *
     * @param element
     */
    @Override
    public void add(E element) {
        //     
        Node<E> node = new Node<>(element, null);
        //      
        Node tail = getTail();
        //      
        if (tail == null) { //        ，            
            //      ，             
            this.head = node;
        } else {
            tail.next = node;
        }
        //        
        this.size++;
    }
    /**
     *     
     */
    private Node getTail() {
        //          
        if (this.head == null) {
            return null;
        }
        //      
        Node node = this.head;
        while (true) {
            if (node.next == null) {
                break;
            }
            node = node.next; //          
        }
        return node;
    }
    /**
     *            
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        //   index    
        this.checkIndex(index);
        //           
        Node<E> node = this.getNode(index);
        //           
        return node.item;
    }
    /**
     *  index    
     */
    private void checkIndex(int index) {
        // 0<=index<size
        if (!(index >= 0 && index < this.size)) {
            throw new IndexOutOfBoundsException("Index: " + index + "   this.size: " + this.size);
        }
    }
    /**
     *         
     */
    private Node<E> getNode(int index) {
        Node<E> node = this.head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }
    /**
     *        
     *
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }
    /**
     *           
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        //   index   
        this.checkIndex(index);
        //           
        Node<E> node = getNode(index);
        //            
        E item = node.item;
        //               
        //                
        if (this.head == node) {
            this.head = node.next;
        } else {
            Node<E> temp = this.head;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next; //    temp                
            }
            temp.next = node.next; //                        
        }
        //                null
        node.next = null;
        //       
        this.size--;
        //       
        return item;
    }
    /**
     *       ：             1，2，3， 1 2     4，      1->2     1->4 4->2          node，          node       node
     */
    public void insert(int index, E element) {
        //                     
        Node<E> item = getNode(index);
        //              
        Node<E> eNode = new Node<>(element, null);
        //       ，         ，        head
        if (index == 0){
            // index==0         
            this.head = eNode;
            eNode.next = item;
            this.size++;
        }else {
            //                            
            Node<E> before = this.head; //        
            for (int i = 0; i < index - 1; i++) {
                before = before.next; //    before            
            }
            before.next = eNode;
            eNode.next = item;
            this.size++;
        }
    }
    public static void main(String[] args) {
        MySinglyLinkedList<String> list = new MySinglyLinkedList<>();
        System.out.println("      ------------------------");
        list.add((String) "a");
        list.add((String) "b");
        list.add((String) "c");
        list.add((String) "d");
        System.out.println("      -------------------------
");
        System.out.println("       ");
        list.insert(0,"f");
        for (int i = 0; i < list.size; i++) {
            System.out.println(list.get(i));
        }
    }
}

양 방향 링크
어제 단 방향 링크 와 스 택 구 조 를 다 쓴 후에 정 걸 이 큰 책 에서 양 방향 링크 를 소개 하 는 부분 을 보 았 다.비록 c 언어 로 썼 지만,나 는 자바 로 번역 해 냈 다.
사고방식 은 다음 과 같다.
먼저,양 방향 링크 와 단 방향 링크 의 가장 큰 차 이 는 양 방향 링크 가 단일 링크 보다 앞 노드 를 가리 키 는 지침 이 많다 는 것 이다.코드 량 은 사실 단일 체인 표 보다 많 지 않 고 사고방식 의 전환 만 극복 해 야 한다.
그 다음으로 요 소 를 삽입 할 때 우 리 는 링크 의 머리 에 삽입 할 수도 있 고 링크 의 끝 에 삽입 할 수도 있다(두 개의 지침 이 있 기 때 문).
부호화
코드 는 사실 싱글 체인 시트 와 차이 가 많 지 않 습 니 다.관심 이 있 으 면 제 가 전에 쓴 싱글 체인 시트 의 글 을 보 세 요.비록 문필 이 매우 엉망 이지 만 코드 는 정말 값 이 싸다.

package com.zxy.lianbiao;
/**
 * @Author Zxy
 * @Date 2021/2/4 20:11
 * @Version 1.0
 */
/**
 *                
 *
 * @param <E>
 */
public class MyDoublyLinkedList<E> implements MyList<E> {

    /**
     *           
     */
    class Node<E> {
        E item; //     
        Node<E> prev; //          
        Node<E> next; //          
        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }
    private Node head; //      
    private Node tail; //      
    private int size; //       
    /**
     *              
     *
     * @param element
     */
    @Override
    public void add(E element) {
        linkLast(element);
    }
    /**
     *                
     */
    private void linkLast(E element) {
        Node t = this.tail; //      
        Node<E> node = new Node<>(t, element, null); //       
        this.tail = node; //                             
        if (t == null) {
            //          ，        
            this.head = node;
        } else {
            t.next = node;
        }
        this.size++;
    }
    /**
     *           
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        this.checkIndex(index);
        //           
        Node<E> node = this.getNode(index);
        return node.item;
    }
    /**
     *  index      
     */
    private void checkIndex(int index) {
        if (!(index >= 0 && index < this.size)) {
            throw new IndexOutOfBoundsException();
        }
    }
    /**
     *             
     */
    private Node getNode(int index) {
        //                          
        if (index < (this.size >> 1)) {
            Node node = this.head;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node node = this.tail;
            for (int i = this.size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
    /**
     *        
     *
     * @return
     */
    @Override
    public int size() {
        return this.size;
    }
    /**
     *     
     *
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        //  index       
        this.checkIndex(index);
        Node node = this.getNode(index); //            
        //          
        E item = (E) node.item;
        //             
        if (node.prev == null) {
            this.head = node.next;
        } else {
            node.prev.next = node.next;
        }
        //             
        if (node.next == null) {
            // node.prev.next = null;
            this.tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
        //                
        node.next = null;
        //                 
        node.prev = null;
        node.item = null;
        this.size--;
        return item;
    }
    /**
     *            
     */
    public void addFirst(E element) {
        this.linkFirst(element);
    }
    /**
     *          
     *
     * @param element
     */
    public void linkFirst(E element) {
        //        
        Node head = this.head;
        Node<E> eNode = new Node<>(null, element, head);
        //           
        this.head = eNode;
        if (head == null) {
            //     ，                          
            this.tail = eNode;
        } else {
            head.prev = eNode;
        }
        this.size++;
    }
    /**
     *           
     *
     * @param element
     */
    public void addLast(E element) {
        this.linkLast(element);
    }
    public static void main(String[] args) {
        MyDoublyLinkedList<String> list = new MyDoublyLinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        System.out.println(list.remove(2));
        System.out.println(list.size);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}

총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!