数据结构---链表以及LinkedList源码分析

痛定思痛。 2024-04-18 15:21 33阅读 0赞

链表是通过一组任意的存储单元来存储线性结构的数组元素的，为了建立起数据元素之间的线性关系，对于链表的每个节点，除了数据元素的自身信息外，还需要存放后继元素的存放地址（单链表），还有双链表存放前置元素和后置元素的存放地址。还有循环链表，将单链表的首尾相连组成环。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70][]

单链表的实现：

public class LinkNode<V> {
    	//数据
    	V data;
    	//下一个节点
    	LinkNode<V> next =null;
    	public LinkNode(V data,LinkNode<V> next) {
    		this.data=data;
    		this.next=next;
    	}
    }
    
    
    public class LinkListDemo<V> {
    	// 初始化头节点
    	LinkNode<V> header = new LinkNode<V>(null, null);
    	LinkNode<V> last = header;
    	int size = 0;
    
    	/*
    	 * 添加元素 头部插入
    	 */
    	public void addToHeader(V data) {
    		LinkNode<V> node = new LinkNode<V>(data, null);
    		// 第一次插入
    		if (header.next == null) {
    			header.next = node;
    			last = node;
    		} else {
    			node.next = header.next;
    			header.next = node;
    		}
    		size++;
    	}
    
    	/*
    	 * 添加元素 尾部插入
    	 */
    	public void addToLast(V data) {
    		LinkNode<V> node = new LinkNode<V>(data, null);
    		last.next = node;
    		last = node;
    		size++;
    	}
    
    	/*
    	 * 删除节点 通过位置删除
    	 */
    	public void removeNode(int index) {
    		if (index > size-1) {
    			System.err.println("index超出范围");
    			return;
    		}
    		LinkNode<V> node = header;
    		// 找到该节点
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		// 修改待删除节点的前一个节点指向
    		node.next = node.next.next;
    		size--;
    	}
    
    	/*
    	 * 删除节点 通过data删除
    	 */
    	public void removeNode(V data) {
    		LinkNode<V> node = header;
    		while (true) {
    			// 找到元素
    			if (node.next != null && node.next.data.equals(data)) {
    				// 删除尾元素的时调整last位置
    				if (node.next == last) {
    					last = node;
    				}
    				node.next = node.next.next;
    				size--;
    				return;
    			} else if (node.next == null) {
    				System.err.println("没有此元素");
    				return;
    			}
    			node = node.next;
    		}
    	}
    
    	/*
    	 * 查找节点
    	 */
    	public V search(int index) {
    		if (index > size-1) {
    			System.err.println("index超出范围");
    			return null;
    		}
    		LinkNode<V> node = header;
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		return node.data;
    	}
    
    	/*
    	 * 更新节点
    	 */
    	public boolean unpdata(int index, V data) {
    		if (index > size-1) {
    			System.err.println("index超出范围");
    			return false;
    		}
    		LinkNode<V> node = header;
    		for (int i = 0; i < index; i++) {
    			node = node.next;
    		}
    		node.data = data;
    		return true;
    	}
    }

这个测试的时候遇到一个小问题：

public static void main(String[] args) {
    		LinkListDemo<Integer> link = new LinkListDemo<>();
    		link.addToHeader(11);
    		link.addToHeader(12);
    		link.addToHeader(13);
    		link.addToHeader(14);
    		link.addToHeader(15);
    		
    		link.removeNode(10);
    		link.removeNode((Integer)15);
    		link.unpdata(3, 10000);
    		int temp = link.search(3);
    		System.out.println(temp);
    	}

由于自动拆装箱的时候，要调用的时候注意参数类型，不得不说好轮子不好造啊。

双向链表实现：

public class DoubleNode<V> {
    	V data;
    	DoubleNode<V> next;
    	DoubleNode<V> prev;
    	public DoubleNode(V data,DoubleNode<V> next,DoubleNode<V> prev) {
    		this.data=data;
    		this.next=next;
    		this.prev=prev;
    	}
    }
    
    
    public class DoubleLinkDemo<V> {
    		//初始化头节点
    		DoubleNode<V> header = new DoubleNode<V>(null, null,null);
    		DoubleNode<V> last=header;
    		int size=0;
    		
    		/*
    		 * 添加元素
    		 * 头部插入
    		 */
    		public void addToHeader(V data) {
    			DoubleNode<V> node = new DoubleNode<V>(data, null,null);
    			//第一次插入
    			if(header.next==null) {
    				header.next=node;
    				node.prev=header;
    				last=node;
    			}else {
    				node.next=header.next;
    				node.prev=header;
    				node.next.prev=node;
    				header.next=node;
    			}
    			size++;
    		}
    		/*
    		 * 添加元素
    		 * 尾部插入
    		 */
    		public void addToLast(V data) {
    			DoubleNode<V> node = new DoubleNode<V>(data, null,null);
    			last.next=node;
    			node.prev=last;
    			last=node;
    			size++;
    		}
    		/*
    		 * 删除节点
    		 * 通过位置删除
    		 */
    		public void removeNode(int index) {
    			if(index>size-1) {
    				System.err.println("index超出范围");
    				return;
    			}
    			//判断一下位置，从前找还是从后找更快
    			if(index>size/2) {
    				DoubleNode<V> node = last;
    				//找到该节点
    				for(int i=size;i>index-1;i--) {
    					node=node.prev;
    				}
    				//修改待删除节点的前一个节点指向,以及后一个节点指向
    				node.next=node.next.next;
    				node.next.prev=node;
    			}else {
    				DoubleNode<V> node = header;
    				//找到该节点
    				for(int i=0;i<index;i++) {
    					node=node.next;
    				}
    				//修改待删除节点的前一个节点指向,以及后一个节点指向
    				node.next=node.next.next;
    				node.next.prev=node;
    			}
    			size--;
    		}
    		/*
    		 * 删除节点
    		 * 通过data删除
    		 */
    		public void removeNode(V data) {
    			DoubleNode<V> node = header;
    			while(true) {
    				//找到元素
    				if(node.next!=null&&node.next.data.equals(data)) {
    					//删除尾元素的时调整last位置
    					if(node.next==last) {
    						last=node;
    					}
    					node.next=node.next.next;
    					node.next.prev=node;
    					size--;
    					return;
    				}else if(node.next== null) {
    					System.err.println("没有此元素"); 
    					return;
    				}
    				node=node.next;
    			}
    		}
    		/*
    		 * 查找节点
    		 */
    		public V search(int index) {
    			if(index>size-1) {
    				System.err.println("index超出范围");
    				return null;
    			}
    			DoubleNode<V>  node = null;
    			if(index>size/2) {
    				node = last;
    				for(int i=size;i>=index;i--) {
    					node=node.prev;
    				}
    				return node.data;
    			}else {
    				node = header;
    				for(int i=0;i<=index;i++) {
    					node=node.next;
    				}
    				return node.data;
    			}
    		}
    		/*
    		 * 更新节点
    		 */
    		public boolean unpdata(int index,V data) {
    			if(index>size-1) {
    				System.err.println("index超出范围");
    				return false;
    			}
    			DoubleNode<V> node = header;
    			for(int i=0;i<index;i++) {
    				node=node.next;
    			}
    			node.data=data;
    			return true;
    		}
    }

下面分析一下LinkedList源码：

//属性：
    //长度
    transient int size = 0;
    //首节点
    transient Node<E> first;
    //尾节点
    transient Node<E> last;
    
    //节点（采用的双向链表）
      private static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }
    //构造方法
     //空构造方法
      public LinkedList() {}
    
    //插入函数
    /*
    *头节点插入
    */
     public void addFirst(E e) {
            linkFirst(e);
        }
      private void linkFirst(E e) {
            final Node<E> f = first;
            final Node<E> newNode = new Node<>(null, e, f);
            first = newNode;
            //判断是否是第一个节点
            if (f == null)
                last = newNode;
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
        
        /*
        *尾节点插入
        */
         public void addLast(E e) {
            linkLast(e);
        }
         public boolean add(E e) {
            linkLast(e);
            return true;
        }
          void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            //同样判断是否为第一个节点
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
        //通过头插和尾插可以看出。linkList中没有头元素（一个空元素起点）
        
     //删除函数
     /*
     *循环找到待删除的元素，源码中对待删除的元素是否为空进行了判断
     */
      public boolean remove(Object o) {
            if (o == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (o.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
            return false;
        }
         E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
            //判断删除后，他的上一个节点是否为首节点
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
            //判断删除后，他的下一个节点是否为尾节点
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }  
        //删除首节点
         private E unlinkLast(Node<E> l) {
            final E element = l.item;
            final Node<E> prev = l.prev;
            l.item = null;
            l.prev = null; // help GC
            last = prev;
            if (prev == null)
                first = null;
            else
                prev.next = null;
            size--;
            modCount++;
            return element;
        }
    
        public E remove(int index) {
            //检查index是否合法
            checkElementIndex(index);
            //通过index查找到对应的值，然后删除
            return unlink(node(index));
        } 
         private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
          private boolean isElementIndex(int index) {
            return index >= 0 && index < size;
        }
        //循环找到index对应的元素
         Node<E> node(int index) {
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
        /*
        *清空函数
        */
         public void clear() {
           //清空所有节点
            for (Node<E> x = first; x != null; ) {
                Node<E> next = x.next;
                x.item = null;
                x.next = null;
                x.prev = null;
                x = next;
            }
            first = last = null;
            size = 0;
            modCount++;
        }
        
        /*
        *获取函数
        */
         public E get(int index) {
             //检查index是否合法
            checkElementIndex(index);
            //循环找到index对应的对应，然后取值
            return node(index).item;
        }
        /*
        *更新函数
        */
         public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }
    //除了这些函数以后还有好多对首节点，尾节点操作的函数，就不一一讨论了。
    //但是下面LinkList封装了队列的操作，瞅上那么一瞅
    /*
    *操作函数
    */
      public void push(E e) {
            addFirst(e);
        }
        
      public E poll() {
            final Node<E> f = first;
            return (f == null) ? null : unlinkFirst(f);
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YWl4aWFvaGFpXzE_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f47586c58b8f41618d2f9399fbf9136f.png