java手撸数据结构–链表(单向、双端)

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

单向链表(无序链表)(Single-Linked List)

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分
(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。链表有一个头节点。

首先定义一个节点类作为链表的节点

/** * 链表节点类 */public class Node {    //节点值    private Integer data;    //下个节点信息    private Node next;    public Node(Integer data, Node next) { this.data = data; this.next = next;    }    public Integer getData() { return data;    }    public void setData(Integer data) { this.data = data;    }    public Node getNext() { return next;    }    public void setNext(Node next) { this.next = next;    }}

我们创建一个类来实现基本的单向链表

/** * 单向链表实现类 */class MySingleLinkedList{    //头节点    private Node head;    public Node getHead() { return head;    }    public void setHead(Node head) { this.head = head;    }｝

1. 插入

    /**     * 头插     */    public void pushHead(int data) { Node node = new Node(data, head); head = node;    }

    /**     * 尾插     */    public void pushTail(int data) { Node node = new Node(data, null); if (head.getData() == null) {     head = node; } Node currentNode = head; while (true) {     if (currentNode.getNext() == null) {  currentNode.setNext(node);  break;     }     currentNode = currentNode.getNext(); }    }

2. 查找

    /**     * 查找指定节点     */    public Node find(int data) { if (head == null) {     return null; } Node node; Node currentNode = head; while (true) {     if (currentNode == null || currentNode.getData() == data) {  node = currentNode;  break;     }     currentNode = currentNode.getNext(); } return node;    }

3. 删除

   /**     * 删除头节点     */    public void deleteHead() { if (head != null) {     head = head.getNext(); }    }

    /**     * 删除尾节点     */    public void deleteTail() { if (head != null) {     Node currentNode = head;     while (true) {  if (currentNode.getNext() == null) {      break;  }  if (currentNode.getNext().getNext() == null) {      currentNode.setNext(null);      break;  }  currentNode = currentNode.getNext();     } }    }

    /**     * 删除指定元素     */    public void delete(int data) { if (head != null) {     if (head.getData() == data) {  deleteHead();  return;     }     //当前节点     Node currentNode = head;     //当前节点父级节点信息     Node dadNode = head;     while ((currentNode = currentNode.getNext()) != null) {  if (currentNode.getData() == data) {      dadNode.setNext(currentNode.getNext());  }  dadNode = currentNode;     } }    }

4. 遍历

   /**     * 遍历     */    public void forEach() { if (head != null) {     Node currentNode = head;     do {  System.out.print(currentNode.getData() + " --> ");     } while ((currentNode = currentNode.getNext()) != null);     System.out.print("null");     System.out.println(); }    }

测试

 Node head = new Node(12, null); MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head); mySingleLinkedList.pushHead(10); mySingleLinkedList.pushTail(99); mySingleLinkedList.pushTail(1); mySingleLinkedList.pushHead(2); mySingleLinkedList.forEach(); mySingleLinkedList.deleteHead(); mySingleLinkedList.deleteTail(); mySingleLinkedList.delete(12); mySingleLinkedList.forEach();

结果

2 --> 10 --> 12 --> 99 --> 1 --> null10 --> 99 --> null

双端链表

双端链表是单向链表周的一种，他在原有的单向链表上加了个尾节点，对于尾部操作更加便捷。

创建一个双端链表实现类

/** * 双端链表实现 */class MyDoubleLinked{    //头节点    private Node head;    // 尾节点    private Node tail;    public Node getHead() { return head;    }    public void setHead(Node head) { this.head = head;    }    public Node getTail() { return tail;    }    public void setTail(Node tail) { this.tail = tail;    }}

1. 插入

    /**     * 头插     */    public void pushHead(int data) { Node node = new Node(data, head); head = node;    }

    /**     * 尾插     *     * @param data     */    public void pushTail(int data) { if (head == null) {     pushHead(data); } else {     Node node = new Node(data, null);     tail.setNext(node);     tail = node; }    }

2. 查找

    /**     * 查找指定节点     */    public Node find(int data) { if (head == null) {     return null; } Node node; Node currentNode = head; while (true) {     if (currentNode == null || currentNode.getData() == data) {  node = currentNode;  break;     }     currentNode = currentNode.getNext(); } return node;    }

3. 删除

    /**     * 删除头节点     */    public void deleteHead() { if (head != null) {     head = head.getNext(); }    }

     /**     * 删除尾节点     */    public void deleteTail() { if (head != null) {     Node currentNode = head;     while (true) {  if (currentNode.getNext() == null) {      break;  }  if (currentNode.getNext().getNext() == null) {      currentNode.setNext(null);      tail = currentNode;      break;  }  currentNode = currentNode.getNext();     } }    }

    /**     * 删除指定元素     */    public void delete(int data) { if (head != null) {     if (head.getData() == data) {  deleteHead();  return;     }     //当前节点     Node currentNode = head;     //当前节点父级节点信息     Node dadNode = head;     while ((currentNode = currentNode.getNext()) != null) {  if (currentNode.getData() == data) {      dadNode.setNext(currentNode.getNext());  }  dadNode = currentNode;     } }    }

4. 遍历

    /**     * 遍历     */    public void forEach() { if (head != null) {     Node currentNode = head;     do {  System.out.print(currentNode.getData() + " --> ");     } while ((currentNode = currentNode.getNext()) != null);     System.out.print("null");     System.out.println(); }    }

测试

 Node head = new Node(12, null); MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head); mySingleLinkedList.pushHead(10); mySingleLinkedList.pushTail(99); mySingleLinkedList.pushTail(1); mySingleLinkedList.pushHead(2); mySingleLinkedList.forEach(); mySingleLinkedList.deleteHead(); mySingleLinkedList.deleteTail(); mySingleLinkedList.delete(12); mySingleLinkedList.forEach();

结果

2 --> 10 --> 12 --> 99 --> 1 --> null10 --> 99 --> null