链表

1 链表 定义

​

---

2 链表代码实现

public class LinkedList<E>{
    private class Node{
        public E e;// 存储数据
        public Node next;// 指向下一个节点
        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }
        public Node(E e){
            this(e,null);
        }
        public Node(){
            this(null,null);
        }
        @Override
        public String toString(){
            return e.toString();
        }
    }
    // 指向链表头
    private Node head;
    private int size;
    public LinkedList(){
        head = null;
        size = 0;
    }
    //  获取链表中元素的个数
    public int getSize(){
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty(){
        return size==0;
    }
}

---

Node.java

 public class Node {
    //Node中维护的数据
       private Object data;
       //下一个元素的引用
       private Node next;
    
    // setters and getters
}

---

3 ⭐️Java实现链表

3.1创建链表(增加节点)

我将head节点定义在成员变量上：

private static Node head = new Node();

首先，我们定义一个类作为节点

• 数据域
• 指针域

public class Node {

    //数据域
    public Integer data;
    
    //指针域，指向下一个节点
    public Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

创建链表(增加节点)

向链表中尾部插入数据：

• 找到尾节点进行插入
• 即使头节点.next为null，不走while循环，也是将头节点与新节点连接的(我已经将head节点初始化过了，因此没必要判断头节点是否为null)～

---

/**
 * 向链表添加数据
 *
 * @param value 要添加的数据
 */
public static void addData(int value) {

    //初始化要加入的节点
    Node newNode = new Node(value);

    //临时节点
    Node temp = head;

    // 找到尾节点
    while (temp.next != null) {
        temp = temp.next;
    }

    // 已经包括了头节点.next为null的情况了～
    temp.next = newNode;

}

---

3.2遍历链表

上面我们已经编写了增加方法，现在遍历一下看一下是否正确～～～

从首节点开始，不断往后面找，直到后面的节点没有数据：

/**
 * 遍历链表
 *
 * @param head 头节点
 */
public static void traverse(Node head) {

    
    //临时节点，从首节点开始
    Node temp = head.next;

    while (temp != null) {

        if (temp.data != null) {
            System.out.println("关注公众号Java3y：" + temp.data);
        }

        //继续下一个
        temp = temp.next;
    }
}

---

---

3.3插入节点

1. 插入一个节点到链表中，首先得判断这个位置是否是合法的，才能进行插入～
2. 找到想要插入的位置的上一个节点就可以了

public void add(int index,E e){
    if(index<0 || index>e)
        throw new IllegalArgumentException("Index is Illegal");
    Node prev = dummyHead;
    for(int i=0;i<index;i++){
        prev = prev.next;
    }
    prev.next = new Node(e,prev.next);
    size++;
}
// 在链表头添加新的元素e
public void addFirst(E e){
    add(0,e);
}
// 在链表尾添加新的元素e
public void addLast(E e){
    add(size,e);
}

public E remove(int index){
    if(index<0 || index>=size)
        throw new IllegalArgumentException("index is Illegal");
    Node prev = dummyHead;
    for(int i=0;i<index;i++){
        prev = prev.next;
    }
    E delNode = prev.next;
    prev.next = prev.next.next; // prev.next = delNode.next;
    delNode.next = null;
    return delNode.e;
}
// 从链表中删除第一个元素，并返回
public E removeFirst(){
    return remove(0);
}
// 从链表中删除最后一个元素，并返回
public E removeLast(){
    return remove(size-1);
}

5 虚拟头结点

---

反转链表