算法－第四版－练习1.3.31解答

拼搏现实的明天。 2022-03-18 07:36 208阅读 0赞

# 题目 #

实现一个嵌套类DoubleNode用来构造双向链表，其中每个结点都含有一个指向前驱元素的引用和一个指向后续元素的引用（如果不存在则为null）。为以下任务实现若干静态方法：在头插入结点、在表尾插入结点、从表头删除结点、从表尾删除结点、在指定结点前插入新结点、在指定结点之后插入新结点、删除指定结点

# 分析 #

先编写一个内部的嵌套类DoubleNode,存在3个类变量Item值,next和previous  
只尝试用一个私有变量first指向链表的第一个元素  
然后按照思路编写方法.先不用静态的.感觉麻烦.用普通的方法

# 代码 #

package hk13;
    
    import edu.princeton.cs.algs4.Stack;
    
    /**
     * @description: ${description}
     * @create: 2019-02-20
     **/
    public class W_1_3_31<Item> {
        private static class DoubleNode<Item> {
            Item item;
            DoubleNode next;
            DoubleNode previous;
        }
    
        private DoubleNode first;
    
        public DoubleNode getFirst() {
            return first;
        }
    
        public boolean isEmpty() {
            return first == null;
        }
    
        public void insertFromHead(Item item) {//从链表头部插入
            DoubleNode old = first;
            first = new DoubleNode();
            first.item = item;
            first.next = old;
            first.previous = null;
            if (old != null) {
                old.previous = first;
            }
    
    
        }
    
        public void insertFromTail(Item item) {//从链表尾部插入
            DoubleNode current = first;
            while (current.next != null) {
                current = current.next;
            }
            DoubleNode last = new DoubleNode();
            last.item = item;
            last.previous = current;
            current.next = last;
        }
    
        public Item deleteFromHead() {//删除链表头部节点
            Item item = (Item) first.item;
            first.next.previous = null;
            first = first.next;
            return item;
        }
    
        public Item deleteFromTail() {//删除链表尾部节点
            DoubleNode current = first;
            while (current.next != null) {
                current = current.next;
            }
            Item item = (Item) current.item;
            current.previous.next = null;
            return item;
        }
    
        public void insertBefore(DoubleNode homeNode, DoubleNode newNode) {//在指定节点的前面插入一个新节点
            homeNode.previous.next = newNode;
            newNode.previous = homeNode.previous;
            newNode.next = homeNode;
            homeNode.previous = newNode;
        }
    
        public void insertAfter(DoubleNode homeNode, DoubleNode newNode) {//在指定节点的后面插入一个新节点
            //这四条语句的顺序不能乱.之前写乱了就会出错
            newNode.next = homeNode.next;
            newNode.previous = homeNode;
    
            homeNode.next.previous = newNode;
            homeNode.next = newNode;
    
        }
    
        public Item deleteNode(DoubleNode deletedNode) {//删除指定节点
            Item item = (Item) deletedNode.item;
            deletedNode.previous.next = deletedNode.next;
            deletedNode.next.previous = deletedNode.previous;
            return item;
        }
    
        public void printLinkedList() {//打印存储的链表结构
            DoubleNode current = first;
            while (current != null) {
                Object item = current.item;
                System.out.print(item + ";");
                current = current.next;
            }
            System.out.println("链表的样子");
        }
    
    
        public static void main(String[] args) {
            DoubleNode<String> x = new DoubleNode<String>();
            DoubleNode<String> y = new DoubleNode<String>();
            x.item = "x";
            y.item = "y";
            W_1_3_31 linkedlist2 = new W_1_3_31();
            linkedlist2.insertFromHead("a");
            linkedlist2.insertFromHead("b");
            linkedlist2.insertFromHead("c");
            linkedlist2.printLinkedList();
            linkedlist2.insertFromTail("d");
            linkedlist2.insertFromTail("e");
            linkedlist2.insertFromTail("f");
            linkedlist2.printLinkedList();
            Object o1 = linkedlist2.deleteFromHead();
            linkedlist2.printLinkedList();
            Object o2 = linkedlist2.deleteFromTail();
            linkedlist2.printLinkedList();
            DoubleNode firstNode = linkedlist2.getFirst();
            DoubleNode secondNode = firstNode.next;
    //        System.out.println(secondNode.item);
            linkedlist2.insertBefore(secondNode, x);
            linkedlist2.printLinkedList();
            linkedlist2.insertAfter(secondNode, y);
            linkedlist2.printLinkedList();
            Object o = linkedlist2.deleteNode(secondNode);
            linkedlist2.printLinkedList();
        }
    }

# 运行结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]  
结果说明:  
1.先从头插入,依次为  
a  
b-a  
c-b-a  
2.从尾插入,依次为  
c-b-a-d  
c-b-a-d-e  
c-b-a-d-e-f  
3.删除头部元素  
b-a-d-e-f  
4.删除尾部元素  
b-a-d-e  
5.先找到第二个元素a.在a的前面插入元素x  
b-x-a-d-e  
6.在a的后面插入元素y  
b-x-a-y-d-e  
7.插入指定元素a  
b-x-y-d-e

# 心得 #

一,有几种特殊情况没有特别考虑:  
1,表里面只有1个节点  
2,表为null  
二,看答案别人,除了用first还用了last  
暂时先这样

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220318/ec169b6e881f45fe9c710d7afd0fd25f.png