概念

检索起点跟单向链表一样

每个节点有指向上一个节点、以及下一个节点的指针

 

双向链表 - 添加节点到尾部

代码实现

class DoubleLinkedList<T> {
   
     
	
	// 链表头指针
	Node<T> headPointer = new Node<T>();
	
	
	public void add(T a) {
   
     
		
		// 1. 添加的元素封装成一个节点
		Node<T> newNode = new Node<T>(a);
		
		// 2. 表示遍历到的节点
		Node<T> temp = headPointer;
		
		// 3. 寻找到 next=null的尾节点
		while(temp.next != null) {
   
     
			temp = temp.next;
		}
		
		// 4. 尾节点的next指向 新节点
		temp.next = newNode;
		
		// 5. 新节点的pre指向 尾节点
		newNode.pre = temp;
		
	}
	
	
	@Override 
	public String toString() {
   
     
		if(headPointer.next == null) {
   
     
			return "";
		}
		Node<T> currentNode = headPointer.next;
		StringBuilder sb = new StringBuilder();
		
		while(currentNode != null) {
   
     
			sb.append(currentNode.toString() + "\n");
			currentNode = currentNode.next;
		}
		sb.delete(sb.lastIndexOf("\n"), sb.length());
		
		return sb.toString();
	}
	
	
	private class Node<T> {
   
     
		T data;
		Node<T> pre;
		Node<T> next;
		
		Node() {
   
     
			data = null;
			pre = null;
			next = null;
		}
		
		Node(T a) {
   
     
			data = a;
			pre = null;
			next = null;
		}
		
		public String toString() {
   
     
			return data.toString();
		}
		
	}
	
}

测试代码

需要添加到链表的类

class Emp {
   
     
	int empno;
	String ename;
	
	Emp(int empno, String ename) {
   
     
		this.empno = empno;
		this.ename =ename;
	}

	@Override
	public String toString() {
   
     
		return "car [empno=" + empno + ", ename=" + ename + "]";
	}
	
}

将上述元素添加到链表

	public static void main(String[] args) {
   
     
    
		Emp emp1 = new Emp(32, "lrc");
		Emp emp2 = new Emp(16, "rwe");
		Emp emp3 = new Emp(79, "bcv");
		DoubleLinkedList<Emp> dll = new DoubleLinkedList<Emp>();
		
		dll.add(emp1);
		dll.add(emp2);
		dll.add(emp3);
		
		System.out.println(dll);
		
	}
}

运行结果

 

双向链表 - 删除节点

代码实现

public void delete(T a) {
   
     

    // 1. 指代当前遍历到的节点
    Node<T> currentNode = headPointer.next;

    // 2. 当前遍历的节点不为空
    while(currentNode != null) {
   
     

        // 3., 一旦遇到 需要删除的节点,结束完以下操作,立即停止遍历
        if(currentNode.data.equals(a)) {
   
     

            // 3.1 需要删除节点的前一个节点的next指针,指向需要删除节点的下一个节点
            currentNode.pre.next = currentNode.next;

            // 3.2 如果删除节点的后面还有节点则 其下一个节点的pre指针指向 删除节点的前一个节点
            if(currentNode.next != null) {
   
     
                currentNode.next.pre = currentNode.pre;
            }

            // 3.3 结束循环
            break;
        }

        // 4. 当前节点不符合要求,遍历移动到下一个节点
        currentNode = currentNode.next;
    }
}

测试代码

public static void main(String[] args) {
   
     
    Emp emp1 = new Emp(32, "lrc");
    Emp emp2 = new Emp(16, "rwe");
    Emp emp3 = new Emp(79, "bcv");
    DoubleLinkedList<Emp> dll = new DoubleLinkedList<Emp>();

    // 添加节点,并打印出来
    dll.add(emp1);
    dll.add(emp2);
    dll.add(emp3);
    System.out.println(dll);

    System.out.println("\n-------------------\n");

    // 删除一个节点,并打印链表存在的节点
    dll.delete(new Emp(79,"bcv"));
    System.out.println(dll);

}

运行结果

 

双向链表 - 逻辑有序添加到链表

public void addOrder(T a) {
   
     

    // 1. 封装添加的元素为数组
    Node<T> newNode = new Node<T>(a);

    // 判断当前链表是否有有效元素,无,则直接在头指针向后加即可
    if (headPointer.next == null) {
   
     
        headPointer.next = newNode;
        newNode.pre = headPointer;
        return;
    }

    // 加一个标志位,看是否有元素添加成功
    boolean flag = false;
    Node<T> currentNode = headPointer;

    while(currentNode.next != null) {
   
     

        // 代表当前遍历到的元素
        currentNode = currentNode.next;

        // 如果遍历的元素大于添加的元素,则把添加的元素插入在当前元素前面
        if(currentNode.data.hashCode() >  newNode.data.hashCode()) {
   
     
            flag = true;
            currentNode.pre.next = newNode;
            newNode.next = currentNode;
            currentNode.pre = newNode;
            newNode.pre = currentNode.pre;
            break;
        }

    }

    // 如果整个链表遍历完毕,依然未找到大于添加元素的值,则直接将添加元素放入链表尾部
    if(!flag) {
   
     
        currentNode.next = newNode;
        newNode.pre = currentNode;
    }
}

测试代码

public static void main(String[] args) {
   
     

    Emp emp1 = new Emp(32, "lrc");
    Emp emp2 = new Emp(16, "rwe");
    Emp emp4 = new Emp(16, "rwetfgdg");
    Emp emp3 = new Emp(79, "bcv");
    DoubleLinkedList<Emp> dll = new DoubleLinkedList<Emp>();

    dll.addOrder(emp1);
    dll.addOrder(emp2);
    dll.addOrder(emp4);
    dll.addOrder(emp3);
    System.out.println(dll);

}

运行结果