线性表-链式结构
-
昨天在学习顺序结构的内容时感觉并不难,但是你会在编写代码的时候发现他的结构的弊端
- 只要是扩容,或者中间插入,那么你必须把数组拷贝来拷贝去的麻烦
- 昨天在测试一千万还是五千万的时候,由于需要分配内存空间,直接涨上1G的使用空间,如果你电脑没有这个内存富余,那么分配空间很可能会会失败掉
- 为了克服上面的问题,那么我们今天来学习饿线性表的链式结构
什么是链表
-
典型的链表结构中的节点包含两部分
- 你需要存储的数据
- 既然叫链式,那么肯定是有下一个数据节点的引用,结构如图
- 如上我们就能很清晰的看到他的结构到底是怎么样的,在链表中,需要有一个"头引用"地址来指向第一个元素,而第一个在指向下一个元素,以此类推,直到某个元素的地址引用为null,表示链表到头了,因为他找不到下一个元素在那里了,所以这个节点就是尾节点,地址为null以表示链表结束
- 与顺序结构的区别
- 打开昨天的文章,我们发现的第一点区别就是链表比顺序多了指向,顺序表的逻辑结构和物理结构是一样的,都是连续地址存放,而链表则不同,他在物理存储的时候并不一定是连续存储的,逻辑上的引用关系通过地址部分的引用变量来实现的
-
好了我们知道了两个表的结构上的区别,所以我们就可以分析出了链表的优势在哪里
- 不像顺序结构需要连续地址,插入或者扩容需要大量移动元素,而链表的处理方式就是直接改变引用就可以了,如下图
- 链表不需要连续存放,因此在保存大量数据的时候,不需要分配一块连续空间,可以动态的插入,比如你要存点A,直接把点A的地址改变到下一个节点地址,然后改变上一个元素地址即可
-
与顺序表相比缺点也是显而易见的,
- 那就是耗费空间,因为他多保存了一个地址引用,但是当你在操作大量元素的时候,这个缺点完全可以忽略
- 还有一个缺点,我们回想昨天的顺序表结构,他取值是直接拿数组下标即可,那么我们分析到这,链表好像没有下表,那么该怎么取得值呢?只能去遍历链表,所以我们总结出链表适合增删,不适合查找修改
链表实现形式
- 单向链表:就是最开始的那种图
- 双向链表:就是单向链表的双地址版,不仅仅保存了下一个节点地址,还保存了上一个节点地址
- 单向循环链表:就是单向链表的尾节点连接到头结点地址上,形成一个回环
- 双向循环链表:就是双向链表的头尾相连,形成回环
头指针和头节点
- 这是两个不同的东西,刚开始自己写代码也是不清楚,所以很头疼,下面这幅图你应该就知道区别了
- 如上图,头指针只是一个指向而已,并不是真正的(数据+地址),仅仅是指向头节点而已,如果有尾指针,那么意思是相同的,也就是只指向最后一个尾节点
单向链表实现
- 单项列表的结构简单,但是在自己的代码实现中,删除操作,需要一个额外的指针
-
如上,因为每个节点中只是保留了你下一个节点的地址,如果你遍历到了这个节点,这个节点就是你要删除的节点,那么你需要做的是把上一个节点和下一个节点链接起来,但是你遍历到此节点后,你上一个节点的信息已经遍历过去了,回不去了,所以我们就需要额外的保存已经遍历过的上一个节点
public class MyLinkedList<T> { //添加的数据的个数 private int size; //头指针 private Node<T> head; //尾指针 private Node<T> tail; public MyLinkedList() { //初始化时候,头指针为空 head = new Node<>(null,null); //因为没有元素,所以头指针尾指针是一个 tail = head; } //添加元素 public void add(int index ,T element) { int i = -1; for (Node<T> x = head; x != null; x = x.behind) { if (i == index -1){ Node<T> next = x.behind; x.behind = new Node<>(next,element); break; } i ++; } size ++; } //增加元素 public void addLast(T element){ //如果头指针指向都是空的那么这个肯定是一个空链表 if (head.behind == null){ //空链表添加,就是新建节点的过程,新建的节点由于是第一个,那么他的后面是没有节点的 head.behind = new Node<>(null,element); //就一个节点,尾指针就指向这个唯一节点 tail = head.behind; }else { //证明链表不为空,由于是在最后添加操作 //需要将tail暂时保存 Node<T> node = tail; //tail指向新节点 tail = new Node<>(null,element); //原来最后一个节点就是现在的尾指针指向的节点 node.behind = tail; } size ++; } //增加元素 public void addFirst(T element){ //之前跟addLast一致 if (head.behind == null){ head.behind = new Node<>(null,element); tail = head.behind; }else { //向最开始添加节点,那么就需要保存最开始节点的引用 Node<T> node = head.behind; //然后头指针指向最新插入的节点,该节点的构造方法中指向原来第一个节点 head.behind = new Node<>(node,element); } size ++ ; } //删除元素 public void remove(T element){ //空链表直接返回 if (null == head.behind) return; Node<T> per; //这就是文章中说的,暂时保存前一个节点引用的 //第一个节点 Node<T> node = head.behind; //头指针 per = head; while (true){ //如果节点的数据与删除数据一致 if (node.element.equals(element)){ //== //就是该节点的前一个节点指向该节点的下一个节点 per.behind = node.behind; //删除完成 size --; break; }else { //如果不一致,就需要将这个节点暂时保存 per = node ; //如果这个节点没有下面的节点了,代表结尾了 if (node.behind == null){ //tail node.behind == null & !equals = no node //到尾节点了,而且尾节点的数据与传入不一致,代表整个链表没有此数据 //退出 break; }else { //代表此node还有下一个节点 //那么就移动指向,移到下一个节点再while判断 node = node.behind; } } } } //跟上面的方法大同小异,而且比上面的逻辑简单 public void remove(int index){ if (null == head.behind) return; Node<T> per; Node<T> node = head.behind; per = head; for (int i = 0; i <= index; i++) { if (i == index){ //== per.behind = node.behind; break; }else { per = node ; if (node.behind == null){ //tail node.behind == null & !equals = no node break; }else { node = node.behind; } } } } //修改元素 public void update(int index,T element){ //为什么是-1.因为下面的循环是从head头指针开始的,头指针是不算数的 int i = -1; for (Node<T> x = head; x != null; x = x.behind) { if (i == index){ x.element = element; break; } i++; } } //查找元素 public int getIndex(T element){ if (head.behind == null ) return -1; int i = 0 ; for (Node<T> x = head.behind; x != null; x = x.behind) { if (x.element.equals(element)){ return i; } i++; } return -1; } //是否包含某个元素 public boolean contains(T element){ if (head.behind == null ) return false; for (Node<T> x = head.behind; x != null; x = x.behind) { if (x.element.equals(element)){ return true; } } return false; } //元素个数 public int getSize() { return size; } //代表图中的data+addr部分 private class Node<T>{ Node<T> behind;//指向后面元素的指针 T element; //当前数据 public Node(Node<T> behind, T element) { this.behind = behind; this.element = element; } } @Override public String toString() { if (head == null){ return "{}"; } Node<T> firstNode = head.behind; Node<T> node = new Node<>(firstNode.behind,firstNode.element); StringBuilder buffer = new StringBuilder(); while (true){ if (node == null){ break; }else { buffer.append(node.element + " , "); node = node.behind; } } return buffer.toString(); } } -
测试
public static void main(String[] args) { MyLinkedList<String> linkedList = new MyLinkedList<>(); linkedList.addLast("1"); linkedList.addLast("2"); linkedList.addLast("3"); linkedList.addLast("4"); linkedList.addLast("5"); linkedList.addFirst("0"); linkedList.addFirst("-1"); System.out.println(linkedList); linkedList.remove("0"); System.out.println(linkedList); linkedList.remove(0); System.out.println(linkedList); linkedList.remove(4); System.out.println(linkedList); linkedList.add(2,"s"); System.out.println(linkedList); linkedList.add(4,"p"); System.out.println(linkedList); linkedList.update(0,"x"); System.out.println(linkedList); linkedList.update(3,"z"); System.out.println(linkedList); int x = linkedList.getIndex("x"); System.out.println(x); int z = linkedList.getIndex("z"); System.out.println(z); boolean x1 = linkedList.contains("x"); System.out.println(x1); System.out.println(linkedList.contains("2")); System.out.println(linkedList.contains("yyy")); } -
结果
-1 , 0 , 1 , 2 , 3 , 4 , 5 , -1 , 1 , 2 , 3 , 4 , 5 , 1 , 2 , 3 , 4 , 5 , 1 , 2 , 3 , 4 , 1 , 2 , s , 3 , 4 , 1 , 2 , s , 3 , p , 4 , x , 2 , s , 3 , p , 4 , x , 2 , s , z , p , 4 , 0 3 true true false - 里面的内部类Node,就是每个节点,里面存放了指向和数据
双向循环链表
- 我们也来实现一个双向的链表,其主要的链接操作,所以如图
- 其实实现的重点在于add方法,如果你可以将上面的单链表的理解了,那么下面的就跟闹着玩似的,自我感觉双向的比单向的好写
-
上面是新增元素的一个过程,拆除原来的互相引用,而转链接到新元素到,那么删除的话,就是一个反过程,将要被删除的元素上的所以指向删除,然后该元素的前一个元素引用该元素后面的元素,后面的元素引用前面的元素,如果该元素为a,那么就是a+1互相引用a-1,知道了最麻烦的步骤,下面就是实现代码
public class DoubleLink<T> { private int size; private Node<T> head; private Node<T> tail; public DoubleLink() { head = new Node<>(); tail = new Node<>(); head.front = tail; head.next = tail; tail.front = head; tail.next = head; } private class Node<T> { private Node<T> front; private T element; private Node<T> next; public Node() { } public Node(Node<T> front, T element, Node<T> next) { this.front = front; this.element = element; this.next = next; } @Override public String toString() { return "" + element; } } //增 public void addLast(T element) { if (0 == size) { Node<T> node = new Node<>(head, element, tail); head.next = node; tail.front = node; } else { Node<T> tailNodeFront = tail.front; Node<T> node = new Node<>(tailNodeFront, element, tail); tailNodeFront.next = node; tail.front = node; } size++; } public void addFirst(T element) { if (0 == size) { Node<T> node = new Node<>(head, element, tail); head.next = node; tail.front = node; } else { Node<T> headNextNode = head.next; Node<T> node = new Node<T>(head, element, headNextNode); head.next = node; headNextNode.front = node; } size++; } public void add(int index, T element) { if (0 == size) { Node<T> node = new Node<>(head, element, tail); head.next = node; tail.front = node; } else { int i = -1; for (Node<T> node = head; node != null; node = node.next) { if (i == index) { Node<T> front = node.front; Node<T> newNode = new Node<>(front, element, node); front.next = newNode; node.front = newNode; break; } i++; } } size++; } //删 public void remove(T element){ for (Node<T> node = head.next; node != null && node.element != null; node = node.next) { if (node.element.equals(element)){ Node<T> front = node.front; Node<T> next = node.next; front.next = next; next.front = front; } } size --; } //改 public void update(int index ,T element){ int i = 0; for (Node<T> node = head.next; node != null && node.element != null; node = node.next) { if (i == index){ node.element = element; } i++; } } //查 public int getIndex(T element){ int i = 0; for (Node<T> node = head.next; node != null && node.element != null; node = node.next) { if (node.element.equals(element)){ return i; } i++; } return -1; } //包含 public boolean contains(T element){ for (Node<T> node = head.next; node != null && node.element != null; node = node.next) { if (node.element.equals(element)){ return true; } } return false; } @Override public String toString() { StringBuilder builder = new StringBuilder(); for (Node<T> node = head.next; node != null&& node.element != null; node = node.next) { builder.append(node.toString()+" "); } return builder.toString(); } } -
测试
public static void main(String[] args) { DoubleLink<String> doubleLink = new DoubleLink<>(); doubleLink.addLast("1"); doubleLink.addLast("2"); doubleLink.addLast("3"); doubleLink.addLast("4"); System.out.println(doubleLink); doubleLink.addFirst("0"); doubleLink.addFirst("-1"); System.out.println(doubleLink); doubleLink.add(2,"ppp"); doubleLink.add(0,"-2"); System.out.println(doubleLink); doubleLink.remove("ppp"); System.out.println(doubleLink); doubleLink.remove("0"); System.out.println(doubleLink); doubleLink.remove("-1"); System.out.println(doubleLink); doubleLink.remove("-2"); System.out.println(doubleLink); doubleLink.update(0,"11"); doubleLink.update(2,"33"); System.out.println(doubleLink); System.out.println(doubleLink.getIndex("2")); System.out.println(doubleLink.getIndex("2xx")); System.out.println(doubleLink.contains("11")); System.out.println(doubleLink.contains("11x")); } -
结果
1 2 3 4 -1 0 1 2 3 4 -2 -1 0 ppp 1 2 3 4 -2 -1 0 1 2 3 4 -2 -1 1 2 3 4 -2 1 2 3 4 1 2 3 4 11 2 33 4 - 只要会写这两个了,那么其他两个也就会了,好了到这就算告一段落了,如果有错,请及时评论提醒我哈!希望能给你带去帮助
