一、接口定义
还是和之前的顺序表一样，定义一个接口。后续通过链表类去实现这个定义的接口。
interface SingleLinkedList { //头插法 void addFirst(int data); //尾插法 void addLast(int data); //任意位置插入,第一个数据节点为0号下标 void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 boolean contains(int key); //删除第一次出现关键字为key的节点 void remove(int key); //删除所有值为key的节点 void removeAllKey(int key); //得到单链表的长度 int size(); void clear(); void display(); }
二、类定义
定义一个链表类，它是由各个节点构成的，因此还需要在链表类内定义一个关于节点的内部类。代码如下：
public class MyLinkedList implements SingleLinkedList { class LinkNode { public int val; public LinkNode next; public LinkNode(int val) { this.val = val; } } public LinkNode head; }
三、方法实现
3.1创建单链表(初始化创建)
每次通过LinkNode类定义的节点去new一个新的节点并通过构造函数设置初始值，节点定义完成后，通过各个节点的next域把各个节点之间联系起来，便成功创建了一个单链表。
public void creatLinkedList() { LinkNode node1 = new LinkNode(12); LinkNode node2 = new LinkNode(23); LinkNode node3 = new LinkNode(34); LinkNode node4 = new LinkNode(45); LinkNode node5 = new LinkNode(56); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; this.head = node1; }
3.2头插法插入节点
//头插法 public void addFirst(int data) { LinkNode newnode = new LinkNode(data); if (this.head == null) { this.head = newnode; } else { newnode.next = this.head; this.head = newnode; } }
3.3尾插法插入节点
尾插法插入节点时，首先要找到单链表的最后一个节点，再去插入
- 注意，找到单链表的最后一个节点，在while循环里面的控制条件是：cur.next!=null，而不是cur!=null，这一点要切记！！！在我们刷题的时候，很多情况下都要去遍历找节点，因此一定要注意。(cur是一个引用，从head开始遍历)
- 下图是while(cur.next!=null),循环条件结束的时候,cur所指向的位置:>
- 下图是while(cur!=null)，循环条件结束的时候，cur所指向的位置:>
public void addLast(int data) { LinkNode newnode = new LinkNode(data); if (this.head == null) { this.head = newnode; return; } LinkNode cur = this.head; while (cur.next != null) { cur = cur.next; } cur.next = newnode; }
3.4指定位置插入节点
在指定位置插入，首先要判断插入位置是否合法。其次，若是在头节点插入，调用头插法即可，若是在尾节点插入，调用尾插法即可。然后，就需要找到指定的位置，此时应该找的是指定位置的前驱节点，通过指定位置的前驱节点的next域指向要插入的节点即可。当然在执行这一步骤之前，我们还需要先把前驱节点的next域所指向的节点交给要插入的节点的next域。
public void addIndex(int index, int data) { if (index < 0 || index > size()) { System.out.println("插入位置不合法:>" + index); return; } if (index == 0) { addFirst(data); return; } if (index == size()) { addLast(data); return; } LinkNode cur = this.head; LinkNode newnode = new LinkNode(data); for (int i = 0; i < index - 1; i++) { cur = cur.next; } newnode.next = cur.next; cur.next = newnode; }
3.5判断节点是否包含在链表中
只需遍历链表，比较节点的值是否和要判断节点的值相等即可。
public boolean contains(int key) { LinkNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; }
3.6删除值为key的节点
要先找到值为key的节点的前驱节点
private LinkNode findPrev(int key) { LinkNode cur = this.head; while ((cur.next != null)) { if (cur.next.val == key) { return cur; } cur = cur.next; } return cur; }
以下图为例，假设删除34:>
public void remove(int key) { if (this.head == null) { System.out.println("链表为空，无法删除!!!"); return; } if (this.head.val == key) { this.head = this.head.next; return; } /* while(cur.next!=null){ //找到要删除节点的前驱 if(cur.next.val==key){ LinkNode del=cur.next; cur.next=del.next; return; }else { cur=cur.next; } }*/ LinkNode prev = findPrev(key); if (prev == null) { System.out.println("无要删除的数字:>" + key); return; } LinkNode del = prev.next; prev.next=del.next; }
3.7删除所有值为key的节点
方法是通过双指针来解决:>
假设删除值为23的所有节点。
cur往前走，发现值为23的节点，进行删除操作:>
删除之后，prev指向了23的下一个节点。
删除完成后，prev不动，cur继续往后遍历:>
当cur这个引用所指向的节点的值不是23是，prev也要继续往前挪:>
如此进行下去，即可删除所有值为23的节点。
下面是实现代码：>
public void removeAllKey(int key) { if (this.head == null) { System.out.println("链表为空!"); return; } LinkNode prev = head; LinkNode cur = head.next; while (cur != null) { if (cur.val == key) { prev.next = cur.next; cur = cur.next; } else { prev = cur; cur = cur.next; } } if (head.val == key) { head = head.next; } }
3.8得到链表长度
很简单，只需通过一个引用遍历即可。如果引用所指的对象不是空，那么计数器+1。
public int size() { LinkNode cur = this.head; int count = 0; while (cur != null) { count++; cur = cur.next; } return count; }
3.9清空链表
public void clear() { LinkNode cur = this.head; while (cur != null) { LinkNode curNext = cur.next; cur.next = null; cur = curNext; } head.next = null; }
3.10显示链表(打印)
public void display(LinkNode newhead) { LinkNode cur = newhead; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); }
