【概念】
一种物理存储结构上的非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序来实现的
也就是说，链表是由一个一个的节点组织起来的，如车厢一般，整体就叫做链表
【链表结构】
节点可以理解为”节点对象“，它有两个域，一个val域，用于存储数据，一个next域，用于存储下一个节点的地址
【单向，不带头，非循环链表】
一般定义一个"head"对象作为链表的头节点
这是最常见的链表类型
【单向，带头，非循环链表】
head这个节点可以认为是一个标志，其val域存储的值不具备实际意义
【单向，带/不带头，循环链表】
【链表的实现】
链表由若干节点构成，这个节点又是一个完整的结构，那么就可以把节点定义为一个”内部类”
public class MySingleLinkedList
{class ListNode // 这就是一个内部类{public int val;public ListNode next; // next域中存放节点的地址，因此next的数据类型是ListNodepublic ListNode(int val) //构造方法{this.val = val;}}public ListNode head;//代表链表的头节点public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);}
}
我们需要让第一个节点和第二个节点之间关联，以此类推
因此使用该代码
通过node1去访问next域，而node2这个引用，引用的是一个完整对象，node2中存放的就是这个对象的地址“0x35”，所以node1中的next域的值被修改为了0x35
所以我们认为，它的指向关系已经有了
因此可写出如下代码
public void createList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(23);ListNode node3 = new ListNode(34);ListNode node4 = new ListNode(45);ListNode node5 = new ListNode(56);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;this.head = node1;//将node1视为头节点}
【遍历每个节点的值，并打印】
public void display()//遍历每个节点的值并打印{ListNode cur = head;//定义cur，让cur遍历，若让head遍历那只能遍历一次，head无法回归最开始的位置while(cur != null){System.out.println(cur.val + " ");cur = cur.next;}System.out.println();}【计算链表大小】
public int size()//计算链表大小{int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}return count;}【头插法】
头插法要修改两个地方，第一个是新节点的next域，第二个是head的指向
需要使用这两行代码
public void addFirst(int val){ListNode node = new ListNode(val);node.next = head;head = node;}这两行代码的顺序不可改变，如果首先执行head=node，那么node.next=head会变成：
它自己指向了自己，后面的节点丢了
总结：插入节点时一般首先绑后边
【尾插法】
首先找到链表的尾巴（cur一直遍历，当cur.next==null时，cur指向了尾巴），然后让cur的next域的值被设置为node的地址（cur.next = node）
public void addLast(int val){ListNode node = new ListNode(val);if(head == null) //整个是空链表时，直接插即可{head = node;return;}ListNode cur = head;while(cur.next != null){cur = cur.next;}cur.next = node;}【任意位置插入】
1.让cur走index-1步，找到要插入的前一个位置
2.“node的next域”被设置为“cur的next域中所存放的地址”(node.next = cur.next)
3.cur的next域被设置为node的地址（cur.next = node）
当index为0，使用头插法，index等于最大长度，使用尾插法，index不合法，抛异常
public void addLast(int val){ListNode node = new ListNode(val);if(head == null) //整个是空链表时，直接插即可{head = node;return;}ListNode cur = head;while(cur.next != null){cur = cur.next;}cur.next = node;}public void addIndex(int index, int val){//1.判断index的合法性try {checkIndex(index);} catch (InterruptedException e) {e.printStackTrace();}//2.index == 0 || index == size()if(index == 0){addFirst(val);return;}if(index == size()){addLast(val);return;}//3.找到index的前一个位置ListNode cur = findIndexSubOne(index);//4.进行链接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}private ListNode findIndexSubOne(int index)//找到index - 1位置{int count = 0;ListNode cur = head;if(count != index - 1){cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws InterruptedException//检查index是否合法{if(index < 0 || index > size()){throw new IndexNotLegalException("index不合法");}}
}public class IndexNotLegalException extends RuntimeException
{public IndexNotLegalException(){}public IndexNotLegalException(String msg){super(msg);}
}public class IndexNotLegalException extends RuntimeException
{public IndexNotLegalException(){}public IndexNotLegalException(String msg){super(msg);}
}
【删除第一次出现关键字为key的节点】
设关键字key为34
1.先找到34的前一个，cur
当cur的next域中所存放地址节点的val域值与关键字相等时，成功找到（cur.next.val = val）
2.找到cur后，定义cur的下一个节点del（ListNode del = cur.next）,随后进行删除，cur的next域被设置为del的next域中所存放的地址(cur.next = del.next)
或者不去定义del，将cur的next域设置为cur下一个节点的next域所存放的地址（cur,next = cur.next.next）
public void remove(int val){//1.找到需要删除的关键字的前一个ListNode cur = head;while(cur.next != null){if(cur.next.val == val){ListNode del = cur.next;cur.next = del.next;return;}cur = cur.next;}}【删除所有关键字key】
设要删除的key为45
1.定义两个节点，cur代表当前需要删除的节点，prev代表当前需要删除节点cur的前驱节点
2.
当cur的val域和要删除的key相符时
将prev的next域设置为cur的next域中存放的地址（prev.next = cur.next）,随后让cur继续往后走（cur = cur.next）
当cur的val域和要删除的key不相符时
prev指向cur(prev = cur)（或者prev指向prev的next域中存放的地址（prev = prev.next））
随后让cur继续往后走（cur = cur.next）
3.如果head的值和要删除的val相符，让headr往后走（head = head.next）
public void removeAllKey(int val){//1，判空if(head == null){return;}//2.定义prev和curListNode prev = head;ListNode cur = head.next;//3.开始判断并删除while(cur != null){if(cur.val == val){prev.next = cur.next;cur = cur.next;}else{prev = cur; //prev = prev.next;cur = cur.next;}}//4.处理头节点if(head.val == val){head = head.next;}}【清空链表】
public void clear(){ListNode cur = head;while(cur != null){ListNode curN = cur.next;cur.next = null;cur = curN;}head = null;}
