3D特效做首页的网站,ainihejian wordpress,用织梦做的网站,医院网站建设的宗旨顺序表和链表区别
ArrayList #xff1a; 底层使用连续的空间#xff0c;可以随机访问某下标的元素#xff0c;时间复杂度为O#xff08;1#xff09; 但是在插入和删除操作的时候#xff0c;需要将该位置的后序元素整体往前或者向后移动#xff0c;时间复杂度为O…顺序表和链表区别
ArrayList 底层使用连续的空间可以随机访问某下标的元素时间复杂度为O1 但是在插入和删除操作的时候需要将该位置的后序元素整体往前或者向后移动时间复杂度为ON 增容需要申请新空间有时候需要拷贝数据释放旧空间这会有不小的消耗。 顺序表的增容一般是2倍增加的势必会有一定的kong’jian浪费例如当前容量为100时需要扩容的话就是将容量增加到200如果只是再插入几个数据就一定会浪费九十几的空间。
既然如此我们就会思考如何减少空间的浪费这时候链表就登场了下面是单链表的示意图 链表由两个部分组成一个是数据域一个是指针域数据域是用来存放数据的指针域是用来存放下一个或者前一个的引用的这样就把数据给串联起来了大家也就不难发现链表的优点就是用多少空间就申请多少空间做到空间不浪费并且在下面的内容你还会感受到链表的插入删除操作效率很高。
链表的分类
链表有8大类带头和不带头单向还是双向循环还是不循环2^3 8种
带头和不带头是指链表有没有一个哨兵节点就是只是充当头结点的作用不存放任何有效的数据。 上面的图片就是不带头的下面的是带头的
单向和双向是指链表的节点是只指向后一个节点的话就是单向的如果链表的节点即指向前一个结点又指向后一个节点的话就是双向的。
循环和不循环是指链表是否头尾相连如果头尾相连就是循环的否则就是不循环的
实现单链表
下面是自己写的IList接口会被单链表拓展
public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();//清空链表public void clear();//打印链表public void display();
}单链表的节点需要一个数据域和一个指针域我们先来写一个静态内部类来构造节点类 static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}}除此之外我们还需要一个头指针来指向第一个节点 public ListNode head;打印
循环遍历链表打印每一个节点的数据这个方法有利于我们的测试 Overridepublic void display() {ListNode cur head;while(cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}头插
在单链表的头部插入一个数据我们需要将新头节点的next指向原先头部的节点然后改变head的指向。 Overridepublic void addFirst(int data) {ListNode node new ListNode(data);node.next head;head node;}尾插
循环遍历单链表找到尾节点然后改变尾节点的指向即可。 这里要注意如果head为空的时候直接赋值就可以了不能直接使用null会报空指针异常所以在循环前面加多一个判断条件即可。 Overridepublic void addLast(int data) {ListNode node new ListNode(data);if(head null) {head node;return;}ListNode cur head;while(cur.next ! null) {cur cur.next;}cur.next node;}求节点总个数
这个很简单直接循环遍历即可。 Overridepublic int size() {ListNode cur head;int count 0;while(cur ! null) {cur cur.next;count;}return count;}指定位置插入
先判断指定的位置有没有越界和之前的顺序表是一样的这里不赘述
public class IndexException extends RuntimeException{public IndexException(String message) {super(message);}
}private void checkIndexInAdd(int index) throws IndexException {if(index 0 || index size()) {throw new IndexException(下标范围不合法);}}我们要先找到index前一个结点因为这个插入操作是对三个节点进行操作的首先先把index的引用放入新结节点的next中然后再把index前一个结点的next改成新结点的引用这是一般情况如果index 0的话就是头插操作为什么要做一个判断因为我们得出的一般规律最后是cur.next node这是建立在新结点前面一定有结点的情况下但是如果是头插的话就不符合了所以头插需要单独说明。 Overridepublic void addIndex(int index, int data) {try{checkIndexInAdd(index);if(index 0) {addFirst(data);return;}//找到index前一个的节点ListNode cur head;for (int i 0; i index - 1; i) {cur cur.next;}ListNode node new ListNode(data);node.next cur.next;cur.next node;} catch (IndexException e) {System.out.println(index 不合法);e.printStackTrace();}}对于插入操作我们要先处理后面的结点避免后面的结点丢失。 contains
是否包含某个元素直接遍历循环即可 Overridepublic boolean contains(int key) {ListNode cur head;while(cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}删除第一次出现的key
删除某个结点的时候由于这是单链表所以我们最好事先拿到删除节点的前一个结点然后我们要考虑一些特殊的情况如果这个链表为空就不需要删除如果要删除的结点就是头结点那么我们就需要改变头指针的指向最后就是一般情况下我们直接修改删除结点的前一个结点的 next 域 就可以了。 private ListNode findFrontNodeOfKey(int key) {ListNode cur head;while(cur ! null) {if(cur.next.val key) {return cur;}cur cur.next;}return null;}Overridepublic void remove(int key) {//空链表if(head null) {return;}//头删if(head.val key) {head head.next;return;}ListNode prev findFrontNodeOfKey(key);if(prev null) {return;//不存在key}ListNode del prev.next;prev.next del.next;}删除所有出现的key
我们使用两个指针一个从头结点开始另一个从头结点的下一个结点开始遍历链表当第二个指针遇到要删除的结点时配合第一个指针完成此工作然后prev不变cur继续移动如果没有遇到删除的结点两个指针是一起继续向后运动。
要注意如果链表为空的话就直接return 避免发生空指针异常
这时候大家一定知道还差一个结点没有判断就是第一个结点所以我们最后还有判断一下头结点。 Overridepublic void removeAllKey(int key) {if(head null) {return;}ListNode prev head;ListNode cur head.next;while(cur ! null) {if(cur.val key) {prev.next cur.next;} else {prev cur;}cur cur.next;}if(head.val key) {head head.next;}}clear
清空链表你可以直接把头指针赋值为null由于链表没有被引用会被JVM自动回收 Overridepublic void clear() {ListNode cur head;while(cur ! null) {ListNode tmp cur.next;cur.next null;cur tmp;}head null;}模拟实现LinkedList LinkedList 是不带头双向的循环的链表 构建节点
双向的意味着有两个节点一个指向前一个结点一个指向后一个结点还有一个头指针指向头节点一个尾指针指向尾节点。 static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;public ListNode last;打印 public void display() {ListNode cur head;while(cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}头插 要注意如果头指针为null意味着链表为空尾指针自然也是null链表为空的话插入新数据要改变头尾指针的指向。 正常情况下是链表至少有一个结点改变原先头节点的prev指向新结点的next也要改变。 public void addFirst(int data) {ListNode node new ListNode(data);if(head null) {head last node;return;}head.prev node;node.next head;head node;}尾插 注意如果尾指针为null时说明链表为空。和上面的头插一样要单独讨论说明。 public void addLast(int data) {ListNode node new ListNode(data);if(last null) {head last node;}last.next node;node.prev last;last node;}求结点个数 public int size() {ListNode cur head;int count 0;while(cur ! null) {count;cur cur.next;}return count;}指定位置插入
先判断index是否合法不合法还是和之前一样抛异常。
public class IndexOutOfBoundException extends RuntimeException {public IndexOutOfBoundException() {super();}public IndexOutOfBoundException(String message) {super(message);}
}private void checkIndexInAdd(int index) throws IndexOutOfBoundException{if(index 0 || index size()) {throw new IndexOutOfBoundException(下标越界);}}我们先讨论一般情况如果待插入的结点正好前后都是由结点的那么我们需要修改三个结点的指针 cur.prev.next node; node.prev cur.prev; node.next cur; cur.prev node; 现在来注意特殊情况如果index 0时就是头插不管怎么样头插就一定要改变头指针所以要单独讨论。换一种思路如果是头插的话cur.prev null 所以 cur.prev.next 一定会报空指针异常。所以头插还是要单独讨论。 那如果是尾插呢尾插意味着 cur null ,还是和头插思考方式一样尾节点一定要改变所以要单独讨论还有cur.prev 一定会报空指针异常。 public void addIndex(int index,int data) {try {checkIndexInAdd(index);if(index 0) {addFirst(data);return;}ListNode node new ListNode(data);ListNode cur head;for (int i 0; i index; i) {cur cur.next;}if(cur null) {addLast(data);return;}cur.prev.next node;node.prev cur.prev;node.next cur;cur.prev node;} catch (IndexOutOfBoundException e) {e.printStackTrace();}}remove 删除第一次出现关键字为key的节点 如果链表为空不能继续删除操作 如果删除头节点就必须改变头指针所以要单独说明 一般情况下需要变动cur前后结点自然会想到cur.prev.next cur.next; cur.next.prev cur.prev; 那如果是尾删呢上面两行代码只有前面一行还能继续用由于是尾删尾节点就要发生改变所以last cur.prev; public void remove(int key) {if(head null) {return;}if(head.val key) {head head.next;if(head ! null) {head.prev null;}return;}ListNode cur head.next;while(cur ! null) {if(cur.val key) {cur.prev.next cur.next;if(cur.next null) {last cur.prev;} else {cur.next.prev cur.prev;}return;}cur cur.next;}}removeAllKey 删除所有值为key的节点 删除所有的key上面我们写了删除第一次出现key的结点这里把代码直接帮过来删掉return就可以继续用但是一定是对的吗 前面的链表判空直接返回没有问题但是头删的话就有问题了假设头节点是你要删除的结点就意味着头指针要发生改变那如果新的头节点又要发生改变呢这里我们选择尽量不改变我们的祖传代码把头删放在最后面去做即可。 public void removeAllKey(int key) {if(head null) {return;}ListNode cur head.next;while(cur ! null) {if(cur.val key) {cur.prev.next cur.next;if(cur.next null) {last cur.prev;} else {cur.next.prev cur.prev;}}cur cur.next;}if(head.val key) {head head.next;if(head ! null) {head.prev null;}}}contains
是否包含key这个元素 public boolean contains(int key) {ListNode cur head;while(cur ! null) {if(cur.val key) {return true;}cur cur.next;}return false;}clear
你可以直接将head 和last都置为null这样链表就会被JVM自动回收。 这里模仿源码的写法源码是一个一个结点都置为null最后头尾指针再置为null public void clear() {ListNode cur head;while(cur ! null) {ListNode tmp cur.next;cur.prev null;cur.next null;cur tmp;}head last null;}LinkedList 使用
Java集合类中给我们提供了LinkedList这是一个无头双向循环链表我们来看一下它里面的方法方法名字和上面我们模拟实现的差不多。
LinkedList 的构造方法 第二个构造方法是可以传入一个对象和之前ArrayList表示二维数组是一个意思。
LinkedList 的方法 要注意LinkedList和ArrayList 的subList是一样的原理截取的list还是原来的对象list只是范围不同并没有创建新的对象。 add默认尾插 注意LinkedList的add方默认是尾插 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println(list);}addAll
尾插一个对象 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println(list);ArrayListInteger list1 new ArrayList();list1.add(10);list1.add(20);list.addAll(list1);System.out.println(list);}遍历链表
直接打印
LinkedList也是重写了toString 方法 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println(list);}for 循环 public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);int size list.size();for (int i 0; i size; i) {System.out.print(list.get(i) );}System.out.println();}for each public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);for(int x : list) {System.out.print(x );}System.out.println();}迭代器 ListIterator 是继承 Iterator 的这两个都可以来遍历链表打印数据。
迭代器的使用可以类似下面的图 whileit.hasNext()hasNext表示是否由下一个数据通过next方法打印下一个数据之后 it 一直向后移动。 Iterator public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println( Iterator );IteratorInteger it list.iterator();while (it.hasNext()) {System.out.print(it.next() );}System.out.println();}ListIterator public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);ListIteratorInteger lit list.listIterator();while (lit.hasNext()) {System.out.print(lit.next() );}System.out.println();}ListIterator(逆向遍历) public static void main(String[] args) {LinkedListInteger list new LinkedList();list.add(1);list.add(2);list.add(3);System.out.println( ListIterator );ListIteratorInteger lit2 list.listIterator(list.size());while (lit2.hasPrevious()) {System.out.print(lit2.previous() );}System.out.println();}listIterator(int n) 可以指定从哪个下标开始遍历链表 ArrrayList 和 LinkedLisrt 的总结 配套练习 http://t.csdnimg.cn/nmObG
