什么是双向链表?由多个节点组成的存储结构,每个节点包含三部分,头指针、数据、尾指针。通过头指针和尾指针我们可以找到存储在不同位置的相邻节点。
我们先自定义一个节点类:
class Node { String data;//存放的字符串 Node front;//头指针 Node next;//尾指针 // 重写构造方法 public Node(String data) { this.data = data; } }
然后定义一个链表类,联系我们熟悉的集合知道,集合在内存中不是连续的,使用他一定需要知道头节点,操作链表也经常用到尾节点,链表大小。链表一般有 添加,删除,取值,修改的方法。代码如下:
public class LinkList { private Node fail;// 用来保存尾节点 private Node head;// 用来保存头节点 private int count = 0;//用来统计元素数量 // 1.在链表后面添加节点数据 public void add(String data) {} // 2.向链表指定索引位置插入值 public void add(int index, String data) {} // 3.移除指定索引元素 public void remove(int index) {} // 4.修改节点数据 public void set(int index, String newData) { // 5.显示链表长度 public int size() {} // 6.得到指定索引位置字符串 public String get(int index) {} //自定义的一个工具方法,用于根据索引找节点 private Node getOneNode(int index) {} }
以上就是我们要准备一些工具,和要实现功能的规划
1.在链表后面添加节点数据。
如何将一个String字符串存入链表?向链表添加数据成功了,我们肯定可以通过遍历链表的方式找到他,如
何遍历?通过每个节点的指针我们可以找到下一个节点。反过来看,我们要向链表存储数据需要第一:我们需要先将字符串封装到一个Node对象里面,第二:将它与链表里的其他节点发生联系,即让最后一个节点指向该节点。注意如果链表为空,这个添加的节点就是这个链表的头,也是尾,但他的头指针,尾指针都为空。实现代码如下:
// 在后面添加节点数据 public void add(String data) { Node n = new Node(data); // 没有头就没有尾,所以先检查是否有头节点 // 注意 节点有3部分,除非 头尾指针指向null否则不要漏掉 if (head == null) { head = n; } else { // 将尾节点的尾指针指向新节点 fail.next = n; //将新节点的头指针指向尾节点 n.front = fail; } //注意:每操作一次链表他的头尾指针,大小都有可能变化,一定要记得! //如果头存在,节点就是尾 fail = n; count++; }
2.向链表指定索引位置插入值
向链表指定位置插入值我们需要,第一:先找到索引位对应的节点,由于根据索引找节点会经常用到,所以我把他提取成了一个方法,代码如下:
// 得到链表指定节点 private Node getOneNode(int index) { //从第一个位置开始计数 int sum = 0; //索引位节点必须存在 if (index < 0 || index >= size()) { throw new RuntimeException("指定下边越界!"); } //从第一个节点开始遍历查找到索引位 Node n = head; while (sum < index) { n = n.next; sum++; // System.out.println("得到元素:"+n+","+sum); } return n; }
第二,我们要将该索引位节点前一个节点尾指针指向新节点,索引位头指针指向新节点。注意如果索引位节点比较特殊,是头节点,将新节点做为头节点,以前的头节点的头指针指向该节点即可。
// 向链表指定索引位置添加插入值 public void add(int index, String data) { // 先找到索引位节点,将新节点接到索引位节点的前一个节点n0的后面,在将新节点接到索 引位节点的前面 Node n = getOneNode(index); // 得到索引位前一个节点 Node n0 = n.front; // 创建新节点 Node newNode = new Node(data); // 如果n为头,新节点为头 if (n0 == null) { //head是全局变量,记得重置 head = newNode; } else { //新节点的头指针指向前一个节点 newNode.front=n0; //前一个节点的尾指针指向新节点 n0.next = newNode; } //将索引位节点头指针指向新节点 n.front = newNode; // 将新节点属性补齐! newNode.next = n; // 链表长度加一,切记! count++; }
3.移除指定的索引元素
怎么移除元素?我们知道元素移除节点后我们遍历链表是找不到它的,为什么找不到呢?因为链表节点没有节点是指向他的,我们就找不到他了。所以,移除节点指向将指向他的指针,指向别的位置。
步骤:和向指定位置插入数据类似,我们需要这么做:第一,先找到索引位对应的节点,通过调用我们前面已
经写好的工具方法即可做到。第二,将索引位节点的前一个节点指向后一个节点,注意考虑特殊情况。头节点
没有前一个节点,我们移除他只需将索引位后一个节点设为头节点,将头指针指向空;尾节点没有后一个节点
,我们只需将索引位前一个节点尾指针指向null,将其设为尾节点。代码如下:
// 移除指定索引元素 public void remove(int index) { Node n = getOneNode(index); // 除了头和尾 将该节点的前一个节点与他的后一个节点连起来 Node n0 = n.front; Node n2 = n.next; if (n0 == null) { //前一个节点为空,即索引位节点为头节点 n2.front = null; head = n2; } else if (n2 == null) { //后一个节点为空,即索引位为尾节点 n0.next = null; fail = n0; } else { //中间节点将索引位前一个节点与后一个节点连起来即可 n0.next = n2; n2.front = n0; } // 链表长度减1 count--; }
4.修改节点数据
步骤:第一,找到索引对应的节点;第二,修改该节点数据。代码如下:
// 修改节点数据 public void set(int index, String newData) { // 先找到指定索引位置的节点 Node n = getOneNode(index); //将该节点的数据修改即可 n.data=newData; }
5.显示链表长度
时时查看count的值即可。代码如下:
// 显示链表长度 public int size() { return count; }
6.得到指定索引位置字符串。
步骤:第一,先找到索引位对应的节点;第二,取出节点属性。代码如下:
// 得到指定索引位置字符串 public String get(int index) { String s = getOneNode(index).data; return s; }
相关推荐
http://msdn.microsoft.com/en-us/library/95z04bas(v=VS.71).aspx 双向链表
双向链表
建立一个长度为n的带头结点的双向链表,使得该链表中的数据元素递增有序排列。(必须使用双向链表完成,数据类型为整型。) Input 第一行:双向表的长度; 第二行:链表中的数据元素。 Output 输出双向链表中...
定义、实现并测试一个双向链表结点类DNode。 链表结点类中包含私有数据成员为两个整数x,y以及左结点指针left及右结点指针right。 包含的函数成员包括: (a)对结点的数据成员赋值setDNodeValues(int,int,DNode* ...
详细的介绍了Linux内核中使用的最频繁的双向链表
实现双向链表的增删改查功能,dos窗口输入输出,可运行,有注释
构建了双向链表,实现了 ...根据表头,和位置,插入一个元素。 5.int sortlist(node *head,int BigHeadflg) 根据表头,和大小头的标记,排序。 6.int deletelist(node *head) 从头删除所有元素。 开发环境VC6.0下通过。
双向链表类定义及测试文件 对应于数据机构与算法分析(c++版)第三版或第二版 Clifford A.Shaffer 重庆大学使用教材
一种支持类模版和函数模版的C++双向链表,实现了各种排序算法(排序原则可定制),包含学生信息的使用示例(VC 6.0、VS2008).
通过建立双向链表,来实现双向查找,增加和删除的功能
本程序是一个关于双向链表的操作,包括插入节点,删除节点,遍历等
循环双向链表,实现了插入、查找特定的节点、删除等功能,是自己花了半天的时间写完的。
用双向链表实现大数阶乘 输入一个不限制大小的数 即可计算出它的阶乘
用模板类实现了一个简单的双向链表domo。
操作系统c++编程实现安全型双向链表,线程的创建,利用线程对链表进行增删改操作,并检验结果是否正确
2.用双向链表做数据结构,编写一个通信录管理系统。本系统应完成以下几方面的功能。 输入信息——enter(); 显示信息——display(); 查找以姓名作为关键字——search(); 删除信息——delete(); 存盘——...
双向链表 - 数据结构与算法 C 双向链表 - 数据结构与算法 C 。。。。。。
c++模板实现双向链表操作如逆序建立双向链表,插入结点等。
排序插入,更具数据查找结点及修改结点数据等功能,链表根据姓名排序 根据姓名查找记录时支持通配符*和?...通配一个字符,字符不分大小。 将工资管理以文件的形式存在磁盘上,每次操作时将管理集调出
包含了双向链表的结点结构体、表头结构体、创建双向链表、销毁双向链表、获取链表长度、清空双向链表、插入一个节点元素(包含异常分析)、按位置删除链表结点(包含异常分析)、按元素删除链表结点、返回一个结点...