java模拟双向链表实现

淡淡的烟草味﹌ 2023-10-18 15:23 95阅读 0赞

**双向链表**也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的**前驱结点**和**后继结点**

下图是双向链表的逻辑结构图，和单链表不同的是，双向链表中每个节点包含两个节点的指针引用，和一个数据域，这两个节点分别指向前一个节点和后一个节点；

双向链表的这种结构比起单链表，其改进之处正在于此，通过对前后节点的引用可以使得在整个链表中，通过给定的值，可以从前或者向后遍历，大大提升了遍历查询的效率，一定程度上解决了单链表的性能问题，但与此同时，链表的存储开销也增大了，我们熟悉的linkedList，其底层就是这个原理实现的，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]

废话不多说，相信通过上面的解释大家已经很明白了，下面直接上代码，可以结合代码和图结构理解双向链表，

public class DoubleLinkTest<T> {
    
    	/**
    	 * 内部构造节点类
    	 * 
    	 * @param <T>
    	 */
    	private class Node<T> {
    		private T data;
    		private Node next; // 指向下一个节点的引用
    		private Node prev; // 指向前一个节点的引用
    
    		public Node(T data) {
    			this.data = data;
    		}
    	}
    
    	private Node<T> head; // 模拟头结点
    	private Node<T> last; // 模拟尾部节点
    	private Node<T> other; // 暂定一个临时节点，用作指针节点
    	private int length;
    
    	public void DoubleLinkTest() {
    		head = new Node<T>(null);
    		last = head;
    		length = 0;
    	}
    
    	public void DoubleLinkTest(T data) {
    		head = new Node<T>(data);
    		last = head;
    		length = 0;
    	}
    
    	/**
    	 * 链表是否为空
    	 * 
    	 * @return
    	 */
    	public boolean isEmpty() {
    		return length == 0;
    	}
    
    	/**
    	 * 普通添加，往链表尾部添加
    	 * 
    	 * @param data
    	 */
    	public void add(T data) {
    		if (isEmpty()) { // 链表为空，新创建一个链表
    			head = new Node<T>(data);
    			last = head;
    			length++;
    		} else {
    			other = new Node<T>(data);
    			other.prev = last;
    			last.next = other; // 将新的节点与原来的尾部节点进行结构上的关联
    			last = other; // other将成为最后一个节点
    			length++;
    		}
    	}
    
    	/**
    	 * 在指定的数据后面添加数据
    	 * 
    	 * @param data
    	 * @param insertData
    	 */
    	public void addAfter(T data, T insertData) {
    		other = head;
    		while (other != null) { // 我们假定这个head是不为空的。
    			if (other.data.equals(data)) {
    				Node<T> t = new Node<T>(insertData);
    				t.prev = other;
    				t.next = other.next;// 对新插入的数据进行一个指向的定义
    				other.next = t;
    
    				if (t.next == null) {
    					last = t;
    				}
    				length++;
    			}
    			other = other.next;
    		}
    	}
    
    	/**
    	 * 删除，删除指定的数据
    	 * 
    	 * @param data
    	 */
    	public void remove(T data) {
    		other = head;// 我们假定这个head是不为空的。
    		while (other != null) {
    			if (other.data.equals(data)) {
    				other.prev.next = other.next;
    				length--;
    			}
    			other = other.next;
    		}
    
    	}
    
    	/**
    	 * 测试打印数据
    	 */
    	public void printList() {
    		other = head;
    		for (int i = 0; i < length; i++) {
    			System.out.println(other.data + "  ");
    			other = other.next;
    		}
    	}
    
    	public static void main(String[] args) {
    
    		DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
    		link.add(1);
    		link.add(2);
    		link.add(3);
    		link.add(5);
    		link.add(6);
    		link.add(7);
    		link.printList();
    
    		System.out.println(" ============== ");
    
    		System.out.println(" ==== 在3后面添加一个数据开始========== ");
    		link.addAfter(3, 99);
    		link.printList();
    
    		System.out.println(" ==== 在3后面添加一个数据结束========== " + "\r\n");
    
    		System.out.println(" ==== 移除一个数据开始========== ");
    		link.remove(99);
    		link.printList();
    		System.out.println(" \r\n");
    
    	}
    
    }

运行main函数，可以看到控制台的打印输出：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190310200156856.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190310201021507.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nY29uZ3lpNDIw,size_16,color_FFFFFF,t_70