数据结构||Java实现双向链表的增添，删除，插入，修改，查询

曾经终败给现在 2021-10-29 22:20 302阅读 0赞

## 双向链表 ##

双向链表是想对于单链表而言的，区别就是你单链表只有一个指针索引，而双向链表拥有两个索引，前指针和后指针，构成双向连接：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70][]

单向链表：只有指向下一个结点的引用（后驱）；

双向链表：既有指向下一个结点的引用（后驱），也有指向上一个结点的引用（前驱）；

### 优点 ###

1.  双向链表在查找元素的时候，速度比之单向链表会更快
2.  拥有前驱后驱，操作更灵活

### 缺点 ###

1.  增加删除结点操作更繁琐一些
2.  占用的资源更多，数据存储率相比单向链表更低（生产中使用单链表比双链表更多）

## 功能实现： ##

class Nodes {
    	Object data;// 链表中的数据
    	Nodes pre; // 前一节点的索引
    	Nodes next;// 下一节点的索引
    
    	public Nodes(Object data) {
    		this.data = data;// 取的元素
    	}
    }
    
    public class LinkList {
    
    	Nodes head;
    	int size;
    	/*
    	 * 定义打印函数
    	 */
    
    	public void print() {
    		Nodes p = head;
    		while (p != null) {
    			System.out.print(p.data + "<->");
    			p = p.next;
    		}
    		System.out.println();
    	}
    
    	/**
    	 * 添加元素
    	 */
    	public Nodes add(Object data) {
    		Nodes newNode = new Nodes(data);
    		if (size == 0) {
    			head = newNode;
    		} else {
    			Nodes target = head;
    			while (target.next != null) {
    				target = target.next;
    			}
    			target.next = newNode;
    			newNode.pre = target;
    		}
    		size++;
    		return newNode;
    	}
    
    	/**
    	 * 插入元素
    	 */
    	public Nodes insert(int index, Object data) {
    		if (index >= size) {
    			return null;
    		}
    		Nodes newNode = new Nodes(data);
    		if (index == 0) {
    			newNode.next = head;
    			head.pre = newNode;
    			head = newNode;
    		} else {
    			Nodes target = head;
    			int pos = 0;
    			while (pos != index) {
    				target = target.next;
    				pos++;
    			}
    			newNode.pre = target.pre;
    			newNode.pre.next = newNode;
    			newNode.next = target;
    		}
    		size++;
    		return newNode;
    	}
    
    	/**
    	 * 删除指定位置元素
    	 * 
    	 * @return
    	 */
    	public void delete(int index) {
    		if (index >= size) {
    			throw new IllegalStateException("无效索引");
    		}
    		if (index == 0) {
    
    			head = head.next;
    		} else {
    			Nodes target = head;
    			int pos = 0;
    			while (pos != index) {
    				target = target.next;
    				pos++;
    			}
    			target.pre.next = target.next;
    		}
    		size--;
    	}
    
    	/**
    	 * 查询元素
    	 */
    	public void find(Object data) {
    		Nodes target = head;
    		while (target.next != null) {
    			if (data.equals(target.data)) {
    				System.out.println("含该值");
    			} else {
    				target = target.next;
    			}
    		}
    		if (target.next == null && data.equals(target.data)) {
    			System.out.println("含该值");
    		}
    		System.out.println("不含该值");
    	}
    
    	public static void main(String[] args) {
    		LinkList list = new LinkList();
    		// 插入结点
    		list.add(10000);
    		list.add(10010);
    		list.add(10086);
    		list.add(12580);
    		list.add(12306);
    		System.out.println("初始链表：");
    		list.print();
    		list.insert(3, 12316);
    		System.out.println("插入链表：");
    		list.print();
    		list.delete(3);
    		System.out.println("删除指定索引链表：");
    		list.print();
    		System.out.println("查询链表：");
    		list.find(12110);
    
    	}
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70]: /images/20211029/353f77fbcadf4484bdd7b86745197f91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2tMaXU_size_16_color_FFFFFF_t_70 1]: /images/20211029/4a161ee4022a4f269dd38c2f44d83ec1.png