Java中双链表的查找、插入、删除等

ゝ一纸荒年。 2022-04-13 03:18 208阅读 0赞

双向链表结构和单向链表的区别：最后一个结点的链接地址上，单向链表是null,而双向链表是表头的链接地址。

即双向链表的head和last互相指向

## 示意图 ##

**![231247423393589.jpg][]**

表头为空

head之前的节点是last=50这个节点 ，head之后的节点是first=10这个节点

last之前是40这个节点，last之后是head这个头节点

## 双向链表删除节点 ##

**![231248185524615.jpg][]**

删除之后    index节点的上一个（20这个节点）的下一个指向index节点的下一个

index节点的下一个（40这个节点）的上一个指向index节点的上一个

双链表添加节点

**![241342164043381.jpg][]**

在index（20这个节点）之前添加

添加之后  新元素为15这个节点

新元素的下一个指向index（20这个节点）

新元素的上一个指向index的上一个（10这个节点）

系元素的上一个（10这个节点）的下一个指向新元素

新元素的下一个（20这个节点）的上一个指向新元素

了解上面内容后总结双向链表操作

1）需要有一个节点内部类Node

2）需要有一个头部head，head没有值

3）链表要实现的操作有：添加add   删除remove  获得get

4）add操作分类：

a）从头部添加，即添加到第一个元素，即在head之后添加

b）从尾部添加，即添加到最后一个元素，即在head之前添加

c）在指定位置index之前添加

d）在指定位置index之后添加

5）remove操作分类：

a）移出first第一个

b）移出last最后一个

c）移出index

package cn.xiaoshan.Collection;
     
    import cn.xiaoshan.Collection.MyLinkedList;
    import cn.xiaoshan.Collection.MyLinkedList.Node;
     
    public class MyLinkedList /*implements List*/{
    	
    	private class Node{
     
    		private Node previous = this; 
    		private Node next = this;
    		private Object value;
    		Node (Object value){
    			this.value = value;
    		}
    		
    		public String toString(){
    			return value.toString();
    		}
    	}
    	
    		private Node head = new Node(null);
    	
    		private int size;
    	
    		public int getSize(){
    		
    		return size;
    	}
     
    	
    	private boolean addFirst(Object value){//在前面添加
    		addAfter(new Node(value),head);
    		return true;
    	}
    	private boolean addlast(Object value){//在后面添加
    		addBefore(new Node(value),head);
    		return true;
    	}
     
    	
    	private boolean add(Object value){//默认在后面添加
    		addlast(value);
    		return true;
    	}
    	private boolean add(int index,Object value){//在指定节点添加，即在指定节点之前添加
    		addBefore(new Node(value),getNode(index));
    		return true;
    	}
    	private Object getValue(int index){//获得指定位置节点的值
    		return getNode(index).value;
    	}
     
    	
    	private boolean remove(int index){//移除指定节点
    		removeNode(getNode(index));
    		return true;
    	}
    	private boolean removeFirst(){//删除前面的节点，从第一个节点开始删除
    		removeNode(head.next);
    		return true;
    	}
    	private boolean removeLast(){//删除后面的节点，从最后一个节点开始删除
    		removeNode(head.previous);
    		return true;
    	}
    	
    	
    	private Node getNode(int index){//获得指定位置的节点
    		if(index<0||index>size)//注意这里判断条件
    			throw new IndexOutOfBoundsException("The Index Outof Bounds");
    		if(index<size/2){
    		Node node = head;
    		for(int i = 0;i<=index;i++){
    			node = node.next;
    		}
    		return node;
    	}
    	else{
    		Node node = head;
    		for(int i=size-1;i>=index;--i){
    			node = node.previous;
    		}
    		return node;
    	}
    }
    	private void addBefore(Node newNode,Node node){//在某个节点前面添加
    		newNode.next = node;
    		newNode.previous = node.previous;
    		newNode.previous.next = newNode;
    		newNode.next.previous = newNode;
    		size++;
    	}
    	private void addAfter(Node newNode,Node node){//在某个节点后面添加
    		newNode.next = node.next;
    		newNode.previous = node;
    		newNode.previous.next = newNode;
    		newNode.next.previous = newNode;
    		++size;
    	}
    	private void removeNode(Node node){//删除某个节点
    		if(size==0)
    		throw new IndexOutOfBoundsException("LinkedList is Empty");
    		node.previous.next = node.next;
    		node.next.previous = node.previous;
    		node.next = null;
    		node.previous = null;
    		--size;
    	}
    	private boolean isEmpty(){
    		return size ==0;
    	}
    	
    	public String toString(){
    		StringBuilder str = new StringBuilder(">");
    		Node node = head;
    		for(int i = 0;i<size;i++){
    				node = node.next;
    				str.append(node.value);
    				str.append(";");
    		}
    		return str.toString();
    	}
    	
    	public static void main(String[] args) {
    		MyLinkedList link = new MyLinkedList();
    		
    		link.add(4);
    		link.add(7);
    		link.add(8);
    		System.out.println(link);
    		link.addFirst(3);
    		link.addFirst(2);
    		link.addFirst(1);
    		System.out.println(link);
    		link.addlast(9);
    		link.addlast(10);
    		System.out.println(link);
    		
    		link.add(4, "5");
    		link.add(5, 6);
    		link.add(0, "在0索引出加上:0");
    		System.out.println(link);
    		link.add(5, "第5个索引添加后获得这个位置的值");
    		System.out.println(link);
    		System.out.println(link.getValue(5));
    		System.out.println(link.getValue(10));
    		System.out.println(link.getValue(11));
    //		System.out.println(link.getValue(15));
    		
    		link.removeFirst();
    		System.out.println(link);
    		
    		link.remove(4);
    		System.out.println(link);
    		
    		System.out.println(link.getSize());
    		
    		
    		link.removeLast();
    		link.removeLast();
    		link.removeLast();
    		link.removeLast();
    		link.removeLast();
    		System.out.println(link);
    		link.removeLast();
    		link.removeLast();
    		link.removeLast();
    		link.removeLast();
    		link.removeLast();
    		System.out.println(link);
    		link.removeLast();
    		
    		
    	}
    }

在index（20这个节点）之前添加

添加之后  新元素为15这个节点

新元素的下一个指向index（20这个节点）

新元素的上一个指向index的上一个（10这个节点）

系元素的上一个（10这个节点）的下一个指向新元素

新元素的下一个（20这个节点）的上一个指向新元素

[231247423393589.jpg]: /images/20220413/620542b35d204df99cc20213acdbc668.png
[231248185524615.jpg]: /images/20220413/8d912d55f8fa4bea9b6dd67bbbd871fd.png
[241342164043381.jpg]: /images/20220413/0cd759b407834937adf9ae32a456b473.png