2013.07.30
上课内容:链表
上节课我们学习了队列,我们知道队列也是由数组来实现的,而数组的新建所要开辟的内存空间是连续的。
而我们这节课要讲的链表是在内存中开辟不连续的空间,每一个节点可以存储不同的数据类型。
链表存储没有顺序,它是由节点组成的,除了根节点和尾节点,每一个节点跟两个节点相连,下面我们来介绍三中链表:
单链表:一个节点由两部分组成:
一个是该节点的数据,这里用data表示。
一个是该节点指向的地址,这里用next表示。
我们从一个根节点开始,给根节点一个data,当我们再建立一个节点时,会把地址给根节点的next,这样,我们再创建一个地址,就会把地址给上一个节点的next,从而达到了连接的效果。
链表的好处就是每新建一个节点时,就会新开辟一段内存空间,删除节点时,就会自动释放,这样能够大大地节省内存空间。
双链表:一个节点由三部分组成:
一个是该节点的数据,用data表示。
一个是该节点指向的地址,用next表示。
一个是指向该节点的地址,用previous表示。
双链表比单链表多了一个指向该节点的地址,这里在做一些东西时也可以大大地提升效率。
比如我们浏览器的按钮,包括前进和后退键,但如果我们只有后面的地址,就要从新开始遍历,会大大地增加时间。
双向循环链表:一个节点同样由三部分组成,与双链表相同。
循环链表是双链表的一个补充,是将双链表首尾想接,就是指向root节点的地址储存在尾节点last。
这样首尾相连围起来就像一个圆圈,从其中任意一个节点访问,都可以访问next和previous节点,没有了双链表的边界条件的问题。
今天我们要实现的是双链表:
首先我们定义一个接口:
public interface NodeLinkedListInterface { /** * 添加节点的方法 * * @param node新添加的节点对象 */ public abstract void add(Node node); /** * 在指定索引位置添加新节点 * * @param node要添加的新节点 * @param index指定的索引位置 */ public abstract void add(Node node, int index); /** * 移除指定的节点 * * @param node要被移除的节点对象 * @return 返回true和false,true表示移除成功,false表示移除失败 */ public abstract boolean remove(Node node); /** * 移除指定所以位置的节点 * * @param index指定要移除的节点索引 * @return 返回true和false,true表示移除成功,false表示移除失败 */ public abstract boolean remove(int index); /** * 获取指定索引位置的节点对象 * * @param index指定的索引位置 * @return 返回节点对象,如果index的范围超出size,则返回null. */ public abstract Node get(int index); /** * 获取双链表中存储的元素总数 * * @return 返回size的值,如果为0则表示链表中没有节点 */ public abstract int size(); }
然后我们定义节点类:
public class Node { //节点的数据 private Object data; //节点的下一个节点 private Node next; //节点的上一个节点 private Node previous; //构造方法 public Node(Object data) { this.data = data; } //构造方法 public Node(Object data, Node next, Node previous) { this.data = data; this.next = next; this.previous = previous; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public Node getPrevious() { return previous; } public void setPrevious(Node previous) { this.previous = previous; } }
最后我们定义链表类来实现这个接口:
public class NodeLinkedList implements NodeLinkedListInterface { private int size = 0; private Node root = null; private Node last = null; /** * 添加节点的方法 * * @param node新添加的节点对象 */ public void add(Node node) { //如果没有节点,将node给根节点 if (root == null) { root = node; } else { //将最后的一个节点的下一个节点设置为node last.setNext(node); //node为last的上一个节点 node.setPrevious(last); } //将node设置为尾节点 last = node; //链表长度加一 size++; } /** * 在指定索引位置添加新节点 * * @param node要添加的新节点 * @param index指定的索引位置 */ public void add(Node node, int index) { //设置临时节点temp为根节点 Node temp = root; //从根节点开始遍历找到第i个节点 for (int i = 0; i < index; i++) { temp = temp.getNext(); } //如果i不在边界 if (index < size - 1 && index > 0) { //将node插入其中,与前后的地址结合起来 temp.getPrevious().setNext(node); node.setPrevious(temp.getPrevious()); temp.setPrevious(node); node.setNext(temp); //链表长度加一 size++; } else if (index == 0) { //如果插在队开头,将node设置为根节点 root.setPrevious(node); node.setNext(root); root = node; //链表长度加一 size++; } else { //将节点添加至末尾 this.add(node); } } /** * 移除指定的节点 * * @param node要被移除的节点对象 * @return 返回true和false,true表示移除成功,false表示移除失败 */ public boolean remove(Node node) { //建立临时节点temp为根节点 Node temp = root; for (int i = 0; i < size; i++) { //循环找出第i个节点 temp = temp.getNext(); //判断第i个节点和node是否相同 if (temp == node) { //如果相同,让temp两端的节点首尾相接 temp.getNext().setPrevious(temp.getPrevious()); temp.getPrevious().setNext(temp.getNext()); //链表长度减一 size--; //返回真 return true; } } //否则返回否 return false; } /** * 移除指定所以位置的节点 * * @param index指定要移除的节点索引 * @return 返回true和false,true表示移除成功,false表示移除失败 */ public boolean remove(int index) { //如果给的i不在链表长度范围内 if (index < 0 || index >= size) { //返回否 return false; }else if(index ==0){ //如果在开头,就让第二个节点为根节点 root = root.getNext(); root.setPrevious(null); //链表长度减一 size--; //返回真 return true; } //设置临时节点node为根节点 Node node = root; //通过循环找到第index个节点 for (int i = 0; i < index; i++) { node = node.getNext(); } //移除这个节点 this.remove(node); //返回真 return true; } /** * 获取指定索引位置的节点对象 * * @param index指定的索引位置 * @return 返回节点对象,如果index的范围超出size,则返回null. */ public Node get(int index) { //如果index超出范围,就返回null if (index < 0 || index >= size) { return null; } //设置node为根节点 Node node = root; //循环找到第index个节点 for (int i = 0; i < index; i++) { node = node.getNext(); } //返回node return node; } /** * 获取双链表中存储的元素总数 * * @return 返回size的值,如果为0则表示链表中没有节点 */ public int size() { return size; } }
对于实现接口的双链表类,我想我的代码还不是很精简,所以欢迎大家提意见,我一定虚心接受~
相关推荐
数据结构实验——链表数据结构实验——链表数据结构实验——链表数据结构实验——链表数据结构实验——链表数据结构实验——链表数据结构实验——链表
C语言数据机构——链表,是有关链表的所有操作,其中的每个函数我都用debug调试过。不会出现错误。
线性表——链表PPT学习教案.pptx
NULL 博文链接:https://canlynet.iteye.com/blog/605687
用c语言写链表归并
绝对自己编写,用链表实现多项式的加减,希望能对大家有帮助!
数据结构课程的链表类的C++实现,搜索,删除,插入,查找等函数
建立一个单链表,显示链表中每个结点的数据,并做删除和插入处理。 实验说明: (1)建立链表是从无到有地建立起一个链表,即一个一个地输入各结点数据,并建立起前后相互链接的关系。 (2)显示链表是将链表中各结点的...
//第8题:复制链表。输入:一个无序正整数链表(输入为0表示终止)。 //输出:三行,每行一个链表,分别满足题目中的三个链表的要求。 //这道题目必须要复制链表,所以说,不能直接将输入的链表作为第一小题的输出,...
输入:两个链表,每个链表均为若干个有序正整数(单个链表中无重复数字), 以0表示一个链表终止,第一个链表为S1,第二个链表为S2。 输出:分三行,分别输出两个集合的并集、差集(S1-S2)和交集。因 为要连续输出三个...
很简洁,实用的小程序,对初学者理解链表性质很有帮助。
对于新手具有参考作用,包括:1.插入一个字符到一个结点中;2.删除一个结点中的字符;3.插入一个结点到链表中;4.删除链表中的一个结点 等
数据结构——循环链表的操作1 数据结构——循环链表的操作1 数据结构——循环链表的操作1 数据结构——循环链表的操作1
数据结构——循环链表的操作1 数据结构——循环链表的操作1 数据结构——循环链表的操作1 数据结构——循环链表的操作1
设单链表A和B均非递减有序,试设计算法,将A和B合并成非递增有序的单链表C,并要求利用原表A和B的结点空间构造表C。
自己的实验代码。数据结构课程的。很简单. 欢迎阅读和交流
C++数据结构——链表,适合初学者,使用数组模拟链表。