跟你说锤子，直接上代码
双向链表
package com.wangge;
import java.util.ArrayList;
import java.util.List;
/**
* @ClassName 链表
* @Description TODO
* @Author Wangzh8QvQ
* @Date 2020/3/1 17:17
* @Version 1.0
*/
public class 链表 {
public static void main(String[] args) {
WzwLinkedList<String> s = new WzwLinkedList<>();
s.add("一");
s.add("树");
s.add("梨");
s.add("花");
// s.add("压");
// s.add("海");
// s.add("棠");
// s.addFirst("<");
// s.addLast(">");
// System.out.println("正向遍历：" + s.traversal());
// System.out.println("反向遍历：" + s.reverseTraversal());
// System.out.println("链表长度：" + s.size);
// System.out.println("移除尾结点后：");
// s.removeLast();
// System.out.println(s.traversal());
// System.out.println("移除首结点后：");
// s.removeFirst();
// System.out.println(s.traversal());
// System.out.println("移除指定结点后：");
// s.remove(2);
// System.out.println("在指定位置增加节点");
// s.add(1,"oo");
// System.out.println(s.traversal());
// System.out.println("返回list");
// List<String> list = s.getList();
// for (String string: list){
// System.out.println(string);
// }
}
}
class WzwLinkedList<T> {
//头结点
Node<T> first;
//尾结点
Node<T> last;
//大小
int size;
WzwLinkedList() {
}
//结点类（一个私有静态内部类）
private 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;
}
}
/**
* 添加元素，默认添加到链表尾
*
* @param data
*/
public void add(T data) {
//使用一个临时变量保存尾结点。
Node lastTmp = last;
//创建新节点，并且lastTmp将作为这个结点的前一个结点。
Node<T> newNode = new Node<>(lastTmp, data, null);
//这个结点将作为新的尾结点。
last = newNode;
if (lastTmp == null)
//如果这个尾结点的前一个节点，即lastTmp节点为null,则此时链表中只有一个节点，它既是首节点，又是尾结点。
first = newNode;
else
//如果这个尾结点的前一个结点不为null,则前个节点的next将指向本节点
lastTmp.next = newNode;
size++;
}
/**
* 在链表首添加元素
*
* @param data
*/
public void addFirst(T data) {
//使用一个临时变量保存头结点。
Node firstTmp = first;
//创建新节点，这个节点将作为新的头结点
Node node = new Node(null, data, firstTmp);
//把移动first指向的位置
first = node;
if (firstTmp != null) {
//原来的首节点可能出现两种情况，一种为null，一种不为null
//当原来的首节点不为null时，它现在就是第二个节点了，把他的prev指向现在的新节点。
firstTmp.prev = node;
}
size++;
}
/**
* 在链表尾添加元素
*
* @param data
*/
public void addLast(T data) {
this.add(data);
}
/**
* 遍历
*
* @return
*/
public StringBuilder traversal() {
//遍历，从头结点开始。
StringBuilder sb = new StringBuilder("[");
Node tmp = this.first;
while (tmp != null) {
sb.append(tmp.item+", ");
tmp = tmp.next;
}
// sb.append("]");
sb.replace(sb.length()-2,sb.length(),"]");
return sb;
}
/**
* 反向遍历
*
* @param
*/
public StringBuilder reverseTraversal() {
//遍历，从尾结点开始。
StringBuilder sb = new StringBuilder("[");
Node tmp = this.last;
while (tmp != null) {
sb.append(tmp.item);
tmp = tmp.prev;
}
sb.replace(sb.length()-2,sb.length(),"]");
return sb;
}
/**
* 返回集合
*/
public List<T> getList(){
List<T> list = new ArrayList<>();
Node<T> tmp = this.first;
while (tmp != null) {
list.add(tmp.item);
tmp = tmp.next;
}
return list;
}
/**
* 删除尾节点
*
* @param
*/
public void removeLast() {
if (size < 1) {
throw new RuntimeException("链表为空，无法尾移除");
}
if (size == 1) {
this.first = null;
this.last = null;
size--;
return;
}
//拿到倒数第二个节点
Node tmp = last.prev;
//让他的下一个指向null
tmp.next = null;
//然后把last指向它
last = tmp;
size--;
}
/**
* 删除首节点
*
* @param
*/
public void removeFirst() {
if (size < 1) {
throw new RuntimeException("链表为空，无法首移除");
}
if (size == 1) {
this.first = null;
this.last = null;
size--;
return;
}
//找到第二个节点
Node n = first.next;
n.prev = null;
first = n;
size--;
}
/**
* 移除指定位置的节点
*/
public void remove(int i) {
if (i < 0 || i > size - 1) {
throw new RuntimeException("错误的索引值。");
}
if (i == 0) {
this.removeFirst();
size--;
return;
}
if (i == size - 1) {
this.removeLast();
size--;
return;
}
Node temp = first.next;
for (int j = 1; true; j++) {
if (i == j) {
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
break;
}
temp = temp.next;
}
size--;
}
/**
* 指定位置增加节点
*/
public void add(int i, T data){
if (i < 0 || i > size - 1) {
throw new RuntimeException("错误的索引值。");
}
if (i == 0) {
this.addFirst(data);
size++;
return;
}
if (i == size - 1) {
this.addLast(data);
size++;
return;
}
Node temp = first.next;
for (int j = 1; true; j++) {
if (i == j) {
Node n = new Node(temp.prev,data,temp);
temp.prev.next = n;
temp.prev = n;
break;
}
temp = temp.next;
}
size++;
}
}
