南京网站建设q润洽网络,网站开发一个网站,网络营销成功的原因,百度联盟目录
前言
1、什么是链表
2、添加元素
3、虚拟头结点
4、查询修改元素
5、删除元素
附#xff1a;完整代码 前言
又到周末了#xff0c;修整了一天#xff0c;继续来写点东西吧#xff0c;今天#xff0c;我们来学习数据结构中的另一种基础的数据结构——链表…目录
前言
1、什么是链表
2、添加元素
3、虚拟头结点
4、查询修改元素
5、删除元素
附完整代码 前言
又到周末了修整了一天继续来写点东西吧今天我们来学习数据结构中的另一种基础的数据结构——链表。话不多说开整吧
1、什么是链表
在说链表之前先来看一下我们之前说的动态数组、栈、队列这几种数据结构它们的底层都是依托于静态数组都是靠resize解决固定容量问题。而今天要说的链表它和上述几种数据结构都不同它是真正的动态数据结构也是最简单的动态数据结构同时它会涉及到计算机领域一个很重要的概念——引用或者指针理解链表能够帮助我们更深入的理解引用这个概念。
链表数据存储在“节点”Node中
class Node {// 存储真正的数据E e; // next是Node类型的对象即next本身又是一个节点指向的是当前节点的下一个节点Node next;
}
链表就像火车每个节点就是一节车厢车厢中存储真正的数据车厢和车厢之间进行连接使得数据整合在一起用户可以方便的在数据上进行查询等操作。 优点真正的动态不需要处理固定容量的问题
缺点丧失了随机访问的能力
2、添加元素
定义链表类LinkedList且定义为泛型类然后定义它的内部类Node这个节点类并且定义两个成员变量头结点和链表的长度。我们分别实现了在链表头部、链表中间及链表尾部添加节点的操作代码实现如下
public class LinkedListE {private Node head;private int size;public LinkedList() {head null;size 0;}// 获取链表中的元素个数public int getSize() {return size;}// 返回链表是否为空public boolean isEmpty() {return size 0;}// 在链表头添加新的元素public void addFirst(E e) {
// Node node new Node(e);
// node.next head;
// head node;head new Node(e, head);size;}// 在链表中间添加元素public void add(int index, E e) {if (index 0 || index size) {throw new IllegalArgumentException(添加失败位置错误);}if (index 0) {addFirst(e);} else {Node prev head;for (int i 0; i index - 1; i) {prev prev.next;}
// Node node new Node(e);
// node.next prev.next;
// prev.next node;prev.next new Node(e, prev.next);size;}}// 在链表末尾添加元素public void addLast(E e) {add(size, e);}private class Node {public E e;public Node next;public Node(E e, Node next) {this.e e;this.next next;}public Node(E e) {this(e, null);}public Node() {this(null, null);}Overridepublic String toString() {return e.toString();}}
}
3、虚拟头结点
我们知道在向链表头添加元素和向链表其它位置添加元素是有区别的因为我们在添加元素时需要找到待添加元素位置之前的一个节点对于链表头来说它没有前一个位置的节点所以才会显得比较特殊因此通常来说有一种技巧可以实现对于链表头添加元素和其它位置添加元素的操作统一起来就是在链表头节点之前再造一个节点该节点不存储任何元素我们称之为虚拟头结点——dummyHead这样对于链表来说它的第一个元素就是dummyHead的next所对应节点的元素注意dummyHead这个位置对应的元素是根本不存在的仅仅是为了逻辑上的统一。
public class LinkedListE {private Node dummyHead;private int size;public LinkedList() {dummyHead new Node(null, null);size 0;}// 在链表中间添加元素public void add(int index, E e) {if (index 0 || index size) {throw new IllegalArgumentException(添加失败位置错误);}Node prev dummyHead;for (int i 0; i index; i) {prev prev.next;}
// Node node new Node(e);
// node.next prev.next;
// prev.next node;prev.next new Node(e, prev.next);size;}// 在链表头添加新的元素public void addFirst(E e) {add(0, e);}// 在链表末尾添加元素public void addLast(E e) {add(size, e);}
}
4、查询修改元素
查询 修改 判断链表中是否包含某个元素 下面来写个测试方法简单测试一下 执行结果如下 5、删除元素 在上一部分的测试代码中我们稍作修改 可以看到我们也得到了想要的结果 OK关于链表的增删改查就已经都说完了今天就先到这里吧再会
祝工作顺利
附完整代码
public class LinkedListE {private Node dummyHead;private int size;public LinkedList() {dummyHead new Node(null, null);size 0;}// 获取链表中的元素个数public int getSize() {return size;}// 返回链表是否为空public boolean isEmpty() {return size 0;}// 在链表中间添加元素public void add(int index, E e) {if (index 0 || index size) {throw new IllegalArgumentException(添加失败位置错误);}Node prev dummyHead;for (int i 0; i index; i) {prev prev.next;}
// Node node new Node(e);
// node.next prev.next;
// prev.next node;prev.next new Node(e, prev.next);size;}// 在链表头添加新的元素public void addFirst(E e) {add(0, e);}// 在链表末尾添加元素public void addLast(E e) {add(size, e);}// 获取链表的第index位置的元素索引在链表中是非常用操作仅做练习使用public E get(int index) {if (index 0 || index size) {throw new IllegalArgumentException(获取失败位置错误);}Node cur dummyHead.next;for (int i 0; i index; i) {cur cur.next;}return cur.e;}// 获取链表的第一个元素public E getFirst() {return get(0);}// 获取链表的最后一个元素public E getLast() {return get(size - 1);}// 修改链表的第index位置的元素public void set(int index, E e) {if (index 0 || index size) {throw new IllegalArgumentException(设置失败位置错误);}Node cur dummyHead.next;for (int i 0; i index; i) {cur cur.next;}cur.e e;}// 查找链表中是否有元素epublic boolean contains(E e) {Node cur dummyHead.next;while (cur ! null) {if (cur.e.equals(e)) {return true;}cur cur.next;}return false;}// 从链表中删除index位置的元素返回删除的元素public E remove(int index) {if (index 0 || index size) {throw new IllegalArgumentException(删除失败位置错误);}Node prev dummyHead;for (int i 0; i index; i) {prev prev.next;}Node retNode prev.next;prev.next retNode.next;retNode.next null;size--;return retNode.e;}// 删除第一个元素public E removeFirst() {return remove(0);}// 删除最后一个元素public E removeLast() {return remove(size - 1);}Overridepublic String toString() {StringBuilder res new StringBuilder();for (Node cur dummyHead.next; cur ! null; cur cur.next) {res.append(cur -);}res.append(NULL);return res.toString();}private class Node {public E e;public Node next;public Node(E e, Node next) {this.e e;this.next next;}public Node(E e) {this(e, null);}public Node() {this(null, null);}Overridepublic String toString() {return e.toString();}}
}
