线性表的Java实现--链式存储(双向链表)
有了单向链表的基础,双向链表的实现就容易多了。
双向链表的一般情况:
增加节点:
删除节点:
双向链表的Java实现:
package com.liuhao.algorithm; public class DuLinkList<T> { /** * 内部类:链表中的一个节点 * * @author liuhao data 节点中的数据 prev 指向前一个节点的引用 next 指向下一个节点的引用 */ private class Node { private T data;// 保存的数据元素 private Node prev;// 指向上一个节点 private Node next;// 指向下一个节点 public Node() { } public Node(T data, Node prev, Node next) { super(); this.data = data; this.prev = prev; this.next = next; } } private Node header;// 头结点 private Node tail;// 尾节点 private int size;// 链表中元素个数 // 创建空链表 public DuLinkList() { header = null; tail = null; } // 已指定数据元素创建链表,只有一个元素 public DuLinkList(T element) { header = new Node(element, null, null); // 只有一个节点,header,tail都指向该节点 tail = header; size++; } // 返回链表长度 public int length() { return size; } // 获取指定位置的数据元素 public T get(int index) { return this.getNodeByIndex(index).data; } // 获取指定位置的节点 private Node getNodeByIndex(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("索引超出线性表范围"); } if (index < size / 2) { Node current = header; for (int i = 0; i < size / 2 && current != null; i++, current = current.next) { if (i == index) { return current; } } } else { Node current = tail; for (int i = size - 1; i >= size / 2 && current != null; i--, current = current.prev) { if (i == index) { return current; } } } return null; } // 按值查询所在的位置 public int locate(T element) { Node current = header; for (int i = 0; i < size - 1 && current != null; i++, current = current.next) { if (element.equals(current.data)) { return i; } } return -1; } // 向指定位置插入元素 public void insert(T element, int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("索引超出线性表范围"); } if (header == null) { this.add(element); } else { if (0 == index) { this.addAtHead(element); } else { Node prev = this.getNodeByIndex(index - 1);// 获取插入节点的前一个节点 Node next = prev.next;// 待插索引处的节点 Node newNode = new Node(element, prev, next);// 新增节点,让它的prev指向之前的节点。next指向之后的节点 prev.next = newNode;// 之前的节点的next指向当前节点 next.prev = newNode;// 之后节点的prev指向当前节点 size++; } } } // 采用尾插法添加新节点 public void add(T element) { // 若还是空表,则将header和tail都指向该元素即可 if (header == null) { header = new Node(element, null, null); tail = header; } else { // 创建信节点,prev指向tail Node newNode = new Node(element, tail, null); // 令tail的next指向新节点 tail.next = newNode; tail = newNode;// 把新节点设为尾节点 } size++; } // 采用头插发添加新节点 public void addAtHead(T element) { Node newNode = new Node(element, null, header); header.prev = newNode; header = newNode; // 如果插入之前是空表 if (tail == null) { tail = header; } size++; } // 删除指定索引处的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("索引超出线性表范围"); } Node del = null; if (index == 0) { del = header; header = header.next; header.prev = null; } else { Node prev = this.getNodeByIndex(index - 1);// 获取索引处之前的节点 del = prev.next;// 获取索引处的节点 // 让之前的节点的next指向下一个节点 prev.next = del.next; // 有可能删除的是最后一个元素,若直接调用next.prev可能会出错 if (del.next != null) { del.next.prev = prev; } //若删除的是最后一个元素,那么就要重置tail; tail = prev; del.prev = null; del.next = null; } size--; return del.data; } // 删除最后一个元素 public T remove() { return this.delete(size - 1); } // 判断是否为空 public boolean isEmpty() { return size == 0; } // 清空线性表 public void clear() { header = null; tail = null; size = 0; } public String toString() { if (size == 0) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = header; current != null; current = current.next) { sb.append(current.data.toString() + ", "); } sb.append("]"); int len = sb.length(); // 删除多余的“,”和空格 return sb.delete(len - 3, len - 2).toString(); } } }
测试代码:
package com.liuhao.test;
import org.junit.Test;
import com.liuhao.algorithm.DuLinkList;
public class DuLinkListTest {
@Test
public void test() {
//测试构造函数
DuLinkList<String> duList = new DuLinkList("好");
System.out.println(duList);
//测试添加元素
duList.add("ni");
duList.add("没");
System.out.println(duList);
//在头部添加
duList.addAtHead("五月");
System.out.println(duList);
//在指定位置添加
duList.insert("摩卡", 2);
System.out.println(duList);
//获取指定位置处的元素
System.out.println("第2个元素是(从0开始计数):" + duList.get(2));
//返回元素索引
System.out.println("摩卡在的位置是:" + duList.locate("摩卡"));
System.out.println("moka所在的位置:" + duList.locate("moka"));
//获取长度
System.out.println("当前线性表的长度:" + duList.length());
//判断是否为空
System.out.println(duList.isEmpty());
//删除最后一个元素
duList.remove();
System.out.println("调用remove()后:" + duList);
//获取长度
System.out.println("当前线性表的长度:" + duList.length());
//删除指定位置处元素
duList.delete(3);
System.out.println("删除第4个元素后:" + duList);
//获取长度
System.out.println("当前线性表的长度:" + duList.length());
//清空
duList.clear();
System.out.println(duList);
//判断是否为空
System.out.println(duList.isEmpty());
}
}
代码获取地址:https://github.com/liuhao123/JavaMore.git
相关推荐
本文件主要包括了线性表的实现-------链式映像,实现了链表的初始化、插入、删除以及其他操作。
本程序的主要目的在于帮助同学熟练掌握线性表的基本操作在链式存储结构上的实现, 链表的优点是“按需分配”,且增删方便,缺点是不能随机访问。在实际当中,有许多应用 是频繁变动,但并不要求随机访问,在这样的...
实现线性表的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作,栈的顺序存储结构、链式存储结构,以及定义在上述结构的基本操作
用链表实现线性表java用链表实现线性表
线性表-链式-不带头节点.c
本文件主要包括线性表的实现------顺序映像。顺序表的初始化、插入、删除以及其他操作。
第二节 线性表-链式存储-链表回顾数组时间复杂度:访问:由于可以随机访问,O(1)插入:O(n)删除:O(n)静态操作:常数时间内完成动态操作:线性时间内完成此
java实现的简单线性表结构,包含顺序存储结构和单向链式存储结构的源码
线性表-算法-数据结构 定义线性表节点的结构.doc
02-第2章线性表第7讲-双向链表和双向循环链表.pdf
该文档饱含了数据结构课程中关于线性表的十二个基本操作的实现。对于不同的线性表的存储结构,利用C语言分别实现相应的算法
JAVA线性表JAVA线性表JAVA线性表JAVA线性表
链式存储结构线性表的java实现,全代码注释,通俗易懂
201-线性表介绍List-T.mp4
在实现链式存储时,可以使用单链表、双链表或循环链表等不同的结构来实现。单链表包含一个指针域,指向下一个节点;双链表包含两个指针域,分别指向前一个节点和后一个节点;循环链表是一种特殊的链表,尾节点的指针...
线性表编程实验-参考代码.pdf
c语言实现线性表的算法-数据结构算法代码实现——线性表的定义(一) 定义线性表节点的结构.pdf
本程序主要目的在于帮助同学熟练掌握线性表的基本 操作在顺序存储结构上的实现,顺序表的优点是可以实现随机存取,用数组对其进行定义, 主要操作时针对数组下标的运算。本实验相对比较简单,通过本实验,对顺序表...