1.在某下标处插入数据
/** * 任意位置插入,第一个数据节点为0号下标 * @param index * @param data * @return */ public void addIndex(int index,int data) throws IndexIsNotLegal { checkIndexIsLegal(index); if (index == 0) { addFirst(data); return; } if (index == size()) { addLast(data); return; } Node node = new Node(data); Node cur = findIndexSubOne(index);//返回的是下标前一个的节点 node.next = cur.next; cur.next = node; } //检查下标的合法性 public void checkIndexIsLegal(int index) throws IndexIsNotLegal { if (index <0 || index > size()) { throw new IndexIsNotLegal("index位置不合法"); } } //找到下标位置前一个位置 public Node findIndexSubOne(int index) { Node cur = head; int count = 0; while(count != index-1) { cur = cur.next; count++; } return cur; }
在某下标插入，我们考虑三种情况。第一种情况我们在链表最左边插入也就是头插，我们可以调用头插函数直接进行插入，第二种情况我们在链表的最右侧插入也就是尾插，我们也可以直接调用尾插函数进行插入。第三种则是在链表中间插入，我们得先找到该数据的前一个节点，然后把该数据的节点给删除掉。
编辑
当我们的下标输入不合法时，运行后就会出现以下情况:
编辑
Test类测试:
public class Test { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.init();//初始化链表 linkedList.addIndex(2,10); linkedList.display();//打印链表 } }
运行后输出:
编辑
2.查找数据
/** * 查找是否包含关键字key是否在单链表当中 * @param key * @return */ public boolean contains(int key){ if (head == null) { return false; } Node var = head; while(var != null) { if (var.val == key) { return true; } var = var.next; } return false; }
查找数据，我们只需要将链表遍历一边即可，因此时间赋值度为O(N)。唯一注意的是，当链表不存在时，我们直接返回false。
Test类中测试:
public class Test { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.init();//初始化链表 System.out.println(linkedList.contains(2));//查找该元素十分偶在链表中 } }
运行后输出:
编辑
3.删除第一次出现数据
/** * 删除第一次出现的关键字key的节点 * @param key */ public void remove(int key){ if (head == null) { return; } if (head.val == key) { head = head.next; return; } Node ret = searchPrev(key); if (ret == null) { return; } Node del = ret.next; ret.next = del.next; } //返回key的上一个节点 public Node searchPrev(int key) { if (head == null){ return null; } Node node = head; while (node.next!=null) { if (node.next.val == key) { return node; } node = node.next; } return null; }
删除第一次出现的元素，我们需要先找到该个元素的前一个节点。我们可以创造一个方法来实现该效果，找到上一个节点后，我们把再把这个元素的节点给跳过即可完成删除。
编辑
Test类测试:
public class Test { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.init();//初始化链表 linkedList.display();//打印链表 linkedList.addLast(2);//尾插一个2 linkedList.remove(2);//删除第一次出现的2 linkedList.display();//打印链表 } }
运行后输出:
编辑
4.删除所有为key的数据
/** * 删除链表中所有的key * @param key */ public void removeAllKey(int key){ Node prev = head; Node vur = head.next; while (vur != null) { if (vur == null) { return; } if (vur.val == key) { prev.next = vur.next; vur = vur.next; }else { prev = vur; vur = vur.next; } } if (head.val == key) { head = head.next; } }
删除链表中所有出现的key，我们只需要设置一个遍历链表的中间量来找到等于key的元素。找到了就跳过该节点，直到到达最后一个节点。注意，整个循环走完后，我们得判断头节点是否为key，是则删除头节点。
编辑
Test类测试:
public class Test { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.init();//初始化链表 linkedList.display();//打印链表 //尾插三个数据 linkedList.addLast(1); linkedList.addLast(1); linkedList.addLast(1); //头插两个数据 linkedList.addFirst(1); linkedList.addFirst(1); linkedList.display();//打印链表 linkedList.removeAllKey(1);//删除所有的1 linkedList.display();//打印链表 } }
运行后输出:
编辑
5.清空链表
/** * 清除单链表中所有的数据 */ public void clear(){ head = null; }
清空链表是最简单的，我们只需要将头节点置为空。这样整个链表就会销毁，从而达到清空链表种所有的元素。
Test类测试:
public class Test { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); linkedList.init();//初始化链表 linkedList.clear();//清空链表 linkedList.display();//打印链表 } }
啥也没输出:
编辑
