链表

链表是一种常见的数据结构，由一系列节点构成，每个节点包含当前节点的数据和一个指针(单向链表)或者两个指针(双向链表)，链表是一种动态的数据结构，可以动态的增删节点。

1.链表的特点

• 逻辑结构：线性结构

• 物理结构：不要求连续的存储空间

• 存储特点：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在代码执行过程中动态创建。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

2.链表的基础操作

2.1增

增加结点的逻辑是：将新增结点的指针域指向后一个结点，然后将原链表中的前一个结点的指针域指向新增的结点。(注意顺序不能颠倒，否则会导致插入位置后面的结点全部丢失)

//头插法
public void addFirst(int data){Node node=new Node(data);node.next=this.head;this.head=node;
}//尾插法
public void addLast(int data){Node node=new Node(data);Node cur=this.head;if(this.head==null){addFirst(data);}else{while (cur.next!=null){cur=cur.next;}cur.next=node;}
}//给定位置插入
public boolean addIndex(int index,int data){Node node=new Node(data);Node cur=this.head;if(index==0){addFirst(data);return true;}else if(index==size()){addLast(data);return true;}if(index<0||index>size()){System.out.println("插入位置不合法");return false;}else{for (int i = 0; i <index-1 ; i++) {cur=cur.next;}//插入节点的尾指向下一个结点的头node.next=cur.next;//链表插入位置元素的下一个结点指向插入元素的头cur.next=node;}return true;
}

2.2删

//删除第一次出现关键字为key的节点    
public void remove(int key){Node cur=this.head;if(cur==null){System.out.println("链表为空，删除错误");return;}else if(cur.val==key&&cur.next==null){this.head=null;return;}else if(this.head.val!=key&&cur.next==null){System.out.println("未找到key");return;}else if(this.head.val==key){this.head=this.head.next;return;}while (cur.next!=null){if(cur.next.val==key){cur.next=cur.next.next;return;}cur=cur.next;}System.out.println("未找到key");
}
// 删除所有值为key的节点    
public void removeAllKey(int key){Node cur=this.head;if(cur==null){System.out.println("链表为空，删除错误");}else if(cur.next==null&&cur.val==key){this.head=null;}else if(cur.next==null&&this.head.val!=key){System.out.println("未找到key");}else if(cur.val==key){this.head=this.head.next;}while (cur.next!=null){if(cur.next.val==key){cur.next=cur.next.next;continue;}cur=cur.next;}
}

3.自定义链表

3.1 自定义单向链表

/*
单链表中的节点。
节点是单向链表中基本的单元。
每一个节点Node都有两个属性：一个属性：是存储的数据。另一个属性：是下一个节点的内存地址。*/
public class Node {// 存储的数据Object data;// 下一个节点的内存地址Node next;public Node(){}public Node(Object data, Node next){this.data = data;this.next = next;}
}

/*
链表类(单向链表)*/
public class Link<E> {// 头节点Node header;private int size = 0;public int size(){return size;}// 向链表中添加元素的方法（向末尾添加）public void add(E data){//public void add(Object data){// 创建一个新的节点对象// 让之前单链表的末尾节点next指向新节点对象。// 有可能这个元素是第一个，也可能是第二个，也可能是第三个。if(header == null){// 说明还没有节点。// new一个新的节点对象，作为头节点对象。// 这个时候的头节点既是一个头节点，又是一个末尾节点。header = new Node(data, null);}else {// 说明头不是空！// 头节点已经存在了！// 找出当前末尾节点，让当前末尾节点的next是新节点。Node currentLastNode = findLast(header);currentLastNode.next = new Node(data, null);}size++;}/*** 专门查找末尾节点的方法。*/private Node findLast(Node node) {if(node.next == null) {// 如果一个节点的next是null// 说明这个节点就是末尾节点。return node;}// 程序能够到这里说明：node不是末尾节点。return findLast(node.next); // 递归算法！}/*// 删除链表中某个数据的方法public void remove(Object obj){//略}// 修改链表中某个数据的方法public void modify(Object newObj){//略}// 查找链表中某个元素的方法。public int find(Object obj){//略}*/
}

3.2 自定义双向链表

/*
双向链表中的节点。*/
public class Node<E> {Node prev;E data;Node next;Node(Node prev, E data, Node next) {this.prev = prev;this.data = data;this.next = next;}
}

/*** 链表类(双向链表)* @author 尚硅谷-宋红康* @create 15:05*/
public class MyLinkedList<E> implements Iterable<E>{private Node first;  //链表的首元素private Node last;   //链表的尾元素private int total;public void add(E e){Node newNode = new Node(last, e, null);if(first == null){first = newNode;}else{last.next = newNode;}last = newNode;total++;}public int size(){return total;}public void delete(Object obj){Node find = findNode(obj);if(find != null){if(find.prev != null){find.prev.next = find.next;}else{first = find.next;}if(find.next != null){find.next.prev = find.prev;}else{last = find.prev;}find.prev = null;find.next = null;find.data = null;total--;}}private Node findNode(Object obj){Node node = first;Node find = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}node = node.next;}}return find;}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value){Node find = findNode(old);if(find != null){find.data = value;}}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node<E> node = first;@Overridepublic boolean hasNext() {return node!=null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}}
}

自定义双链表测试：

package com.atguigu.list;public class MyLinkedListTest {public static void main(String[] args) {MyLinkedList<String> my = new MyLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");my.add("atguigu");System.out.println("一共有：" + my.size());System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的结果：");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替换java,null后：");my.update("java","JAVA");my.update(null,"songhk");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("删除hello，JAVA,null，atguigu后：");my.delete("hello");my.delete("JAVA");my.delete(null);my.delete("atguigu");System.out.println("所有元素：");for (String s : my) {System.out.println(s);}}
}