java【LinkedList底层实现】

双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

下面代码中，不是双向循环链表，而是双向链表，但是头节点和尾节点没有连接起来。

package com.bjsxt.collection;
import java.util.ArrayList;
public class MyLinkedList {
	//和以前定义数组一样
	private Node first;
	private Node last;
	int size=0;//链表里面有几个节点了	
	void add(Node e){
		final Node l=last;//不能被改变
		//如果last不为空
		if(last!=null){
			//设置e的前缀为last的前缀
			e.setProvide(l);
			//设置last的后缀为空
			e.setNext(null);
			//设置e的后缀为last
			last.setNext(e);
			last=e;	
			if(first.next==null){
				first.setNext(e);
			}
		//如果last为空
		}else{
			first=e;
			last=e;
		}
		size++;
	}
	
	//实现遍历功能
	void whileLinkedList(){
		Node mm=first;
		System.out.print("前置节点"+first.provide);
		System.out.print("自身节点"+first.self);
		System.out.print("后置节点"+first.next.self);
		System.out.println("========================");
		for(int i=0;i<size-1;i++){
			Node x=mm.next;
			if(x!=null){
				if(x.provide!=null){
					System.out.print("前置节点"+x.provide.self);
				}
				
				if(x.self!=null){
					System.out.print("自身节点"+x.self);
				}	
				if(x.next!=null){
					System.out.print("后置节点"+x.next.self);
				}
			}	
			if(i==size-2){
				System.out.print("后置节点"+null);
			}
			System.out.println("========================");
			mm=x;
		}
	}
	
	public static void main(String[] args){		
		MyLinkedList myLinkedList =new MyLinkedList();
		for(int i=0;i<200;i++){
			myLinkedList.add(new Node(i));
		}
		System.out.println("现在队列里面有"+myLinkedList.size+"节点");
		System.out.println("第一个节点"+myLinkedList.first.self);
		System.out.println("最后一个节点"+myLinkedList.last.self);
		myLinkedList.whileLinkedList();		
	}
}

//节点，相当于我们集合里存放的一个个单元
//它本身有三个元素 即前驱 后记 及它本身 为了方便我们将self也定义为String,其实他也可以是Object的任意元素
class Node{
	Node provide;
	Object self;
	Node next;
	public Node getProvide() {
		return provide;
	}
	public void setProvide(Node provide) {
		this.provide = provide;
	}
	public Object getSelf() {
		return self;
	}
	public void setSelf(Object self) {
		this.self = self;
	}
	public Node getNext() {
		return next;
	}
	public void setNext(Node next) {
		this.next = next;
	}
	public Node(Node provide, Object self, Node next) {
		super();
		this.provide = provide;
		this.self = self;
		this.next = next;
	}
	public Node() {
		super();
	}
	public Node(Object self) {
		super();
		this.self = self;
	}
}

           

输出结果如下:

现在队列里面有12节点
第一个节点0
最后一个节点11
前置节点null自身节点0后置节点1========================
前置节点0自身节点1后置节点2========================
前置节点1自身节点2后置节点3========================
前置节点2自身节点3后置节点4========================
前置节点3自身节点4后置节点5========================
前置节点4自身节点5后置节点6========================
前置节点5自身节点6后置节点7========================
前置节点6自身节点7后置节点8========================
前置节点7自身节点8后置节点9========================
前置节点8自身节点9后置节点10========================
前置节点9自身节点10后置节点11========================
前置节点10自身节点11后置节点null========================

           

结束语：看起来简单，做起来难，不要做眼高手低的人

v:18612372242 欢迎交流