Java带头傀儡结点与不带头傀儡结点的双向单列表创建，附加部分面试题

作为一名小白，在学习链表中遇到许许多多的困难，只要相信自己可以，多画图帮助自己思考理解，比别人多努力，多写几遍，总会熟练地掌握链表，没有解决不了的困难，只有不努力的人。

带头傀儡结点比较简单，下来先看一下创建代码和测试：

创建

class ListNode{
    public int val;
    public ListNode next;
    public ListNode prev;
    public ListNode (int val){
        this.val = val;
    }
}
public class DoubleList {
    public ListNode puppetHead;//带傀儡节点的头节点
    public ListNode last;
    public DoubleList(){
        this.puppetHead = new ListNode(-1);
    }
    //头插法
    public void addFirst (int data){
        ListNode node = new ListNode(data);
        if (this.puppetHead.next == null) {
            this.puppetHead.next = node;
            node.prev = this.puppetHead;
            this.last = node;
            return;
        }
        node.next = this.puppetHead.next;
        node.next.prev = node;
        this.puppetHead.next = node;
        node.prev = this.puppetHead;
    }
    //尾插法
    public void addLast (int data){
        ListNode node = new ListNode(data);
        if (this.last == null && this.puppetHead.next == null) {
            this.puppetHead.next = node;
            node.prev = this.puppetHead;
            this.last = node;
            return;
        }
        this.last.next = node;
        node.prev = this.last;
        this.last = node;
    }
    //任意位置插入
    public ListNode searchIndex (int index){
        ListNode cur = this.puppetHead.next;
        if (index < 0 && index > size()){
            return null;
        }
        while (index < 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    public void addIndex (int index, int data){
        if (index == 0){
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = searchIndex(index);
        if (cur == null){
            return;
        }
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    //求链表长度
    public int size(){
        ListNode cur = this.puppetHead.next;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
    //打印单链表
    public void display(){
        ListNode cur = this.puppetHead.next;
        while (cur != null){
            System.out.print(cur.val + "  ");
            cur = cur.next;
        }
        System.out.println();
    }
    //清空单列表
    public void clear(){
        puppetHead.next = null;
        this.last = null;
    }
    //查找关键字
    public boolean contains (int key){
        ListNode cur = this.puppetHead.next;
        while (cur != null){
            ListNode curNext = cur.next;
            if (cur.val == key){
                return true;
            }
            cur = curNext;
        }
        return false;
    }
    //删除第一次出现的关键字
    public void remove (int key){
        ListNode cur = this.puppetHead.next;
        while (cur != null) {
            if (cur.val == key){
                if (this.puppetHead.next.val == key){
                    this.puppetHead.next = cur.next;
                    cur.next.prev = this.puppetHead;
                }else {
                    cur.prev.next = cur.next;
                    if (cur.next != null){
                        cur.next.prev = cur.prev;
                    }
                    else {
                        this.last = this.last.prev;
                    }
                }
                return;
            }else {
                cur = cur.next;
            }
        }

    }
    //删除所有关键字
    public void removeAll (int key) {
        ListNode cur = this.puppetHead.next;
        while (cur != null) {
            if (cur.val == key) {
                if (this.puppetHead.next.val == key) {
                    this.puppetHead.next = cur.next;
                    cur.next.prev = this.puppetHead;
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                    } else {
                        this.last = this.last.prev;
                    }

                }
            }
            cur = cur.next;
        }
    }
}

测试：

public class TestDemo {
    public static void main(String[] args) {
        DoubleList doubleList = new DoubleList();
        doubleList.addLast(1);
        doubleList.addLast(1);
        doubleList.addLast(1);
        doubleList.addLast(5);
        doubleList.addLast(1);
        doubleList.addLast(1);
        //doubleList.display();
        //doubleList.addFirst(9);
        //doubleList.display();
       // doubleList.remove(1);
        doubleList.removeAll(1);
        doubleList.display();

    }
}

 

 

不带头傀儡节点的创建

class ListNode{
    public int val;
    public ListNode next;//存储对象引用
    public ListNode prev;
    public ListNode(int val) {
        this.val = val;
    }
}

public class MyTwoList {
    public ListNode head;
    public ListNode last;
    //头插法
    public void addFirst(int val){
        ListNode listnode = new ListNode(val);
        if (this.head == null){
            this.head = listnode;
            this.last = listnode;
        }
        head.prev = listnode;
        listnode.next = head;
        this.head = listnode;
    }
    //尾插法
    public void addLast(int val){
        ListNode listnode = new ListNode(val);
        if (this.head == null){
            this.head = listnode;
            this.last = listnode;
        }
        last.next = listnode;
        listnode.prev = last;
        this.last = listnode;
    }
    //找要插入的位置
    public ListNode search(int index){
        if (index < 0 || index > size()){
            System.out.println("index位置不合法");
        }
        ListNode cur = this.head;
        int count = 0;
        while (index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //在任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int val){
        ListNode listnode = new ListNode(val);
        if (index == 0){
            addFirst(val);
            return;
        }
        if (index == size()){
            addLast(val);
            return;
        }
        ListNode cur = search(index);
        if (cur == null){
            return;
        }
        listnode.next = cur;
        cur.prev.next =listnode;
        listnode.prev = cur.prev;
        cur.prev =listnode;

    }
    //查找是否包含关键字
    public boolean contains(int key){
        ListNode listnode = this.head;
        if (this.head == null){
            return false;
        }
        while (listnode != null){
            if (listnode.val == key){
                return true;
            }
            listnode = listnode.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        ListNode listnode = this.head;
        while (listnode != null) {
            if (listnode.val == key) {
                if (this.head.val == key) {
                    head = head.next;
                    head.prev = null;
                } else if (this.last.val == key) {
                    last = last.prev;
                    last.next = null;
                } else {
                    listnode.prev.next = listnode.next;
                    listnode.next.prev = listnode.prev;
                }
                return;
            }
            listnode = listnode.next;
        }
    }
    //删除所有值位key的节点
    public void removeAllKey(int key){
        ListNode listnode = this.head;
        while (listnode != null) {
            if (listnode.val == key) {
                if (head.val == key) {
                    if (this.head.next == null){
                        this.head = null;
                        return;
                    }
                    head = head.next;
                    head.prev = null;
                } else {
                    listnode.prev.next = listnode.next;
                    if(listnode.next != null){
                        listnode.next.prev = listnode.prev;
                    }else {
                        this.last = this.last.prev;
                    }
                }
            }
            listnode = listnode.next;
        }
    }
    //得到单链表长度
    public int size(){
        int count = 0;
        ListNode listnode = this.head;
        while (listnode != null){
            count++;
            listnode = listnode.next;
        }
        return count;
    }
    //打印单链表
    public void display() {
        ListNode listnode = this.head;
        while (listnode != null){
            System.out.print(listnode.val+" ");
            listnode = listnode.next;
        }
        System.out.println();
    }
    //清空单链表
    public void clear() {
        this.head = null;
        this.last = null;
    }
}

测试：

public class TestDemo {
    public static void main(String[] args){
        MyTwoList myTwoList = new MyTwoList();
        myTwoList.addLast(4);
        myTwoList.addLast(5);
        myTwoList.addLast(3);
        myTwoList.addLast(5);
        myTwoList.addLast(5);
        myTwoList.display();
        myTwoList.remove(4);
        myTwoList.display();
        myTwoList.removeAllKey(5);
        myTwoList.display();
        //myTwoList.clear();
        System.out.println("asdasdsa");
    }

 

本文地址：https://blog.csdn.net/wah369/article/details/109269314