这里有新鲜出炉的Java函数式编程,程序狗速度看过来!
java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要介绍了JAVA 数据结构链表操作循环链表的相关资料,需要的朋友可以参考下
JAVA 链表操作:循环链表
主要分析示例:
一、单链表循环链表
二、双链表循环链表
其中单链表节点和双链表节点类和接口ICommOperate
一、单链表循环链表
- package LinkListTest;
- import java.util.HashMap;
- import java.util.Map;
- public class SingleCycleLinkList implements ICommOperate < SNode > {
- private SNode head = new SNode("HEAD"); // 公共头指针,声明之后不变
- private int size = 0;
- public int getSize() {
- return this.size;
- }
- /*
- * 链表插入,每次往末端插入,判定末端的标准为next是否指向head
- * */
- @Override public boolean insertNode(SNode node) {
- boolean flag = false;
- initLinkList(); // 初始化链表
- if (this.size == 0) { // 空链表
- this.head.setNextNode(node);
- node.setNextNode(this.head);
- } else {
- SNode current = this.head;
- while (current.getNextNode() != this.head) { // 找到末端节点
- current = current.getNextNode();
- }
- current.setNextNode(node);
- node.setNextNode(this.head); // 循坏链表,尾节点指向head
- }
- this.size++;
- flag = true;
- return flag;
- }
- /*
- * 插入链表指定位置pos,从1开始,而pos大于size则插入链表末端
- * */
- @Override public boolean insertPosNode(int pos, SNode node) {
- boolean flag = true;
- SNode current = this.head.getNextNode();
- initLinkList(); // 初始化链表
- if (this.size == 0) { // 链表为空
- this.head.setNextNode(node);
- node.setNextNode(this.head); // 循坏链表,尾节点指向head
- this.size++;
- } else if (this.size < pos) { // pos位置大于链表长度,插入末端
- insertNode(node);
- } else if (pos > 0 && pos <= this.size) { // 链表内节点
- // 1、找到要插入pos位置节点和前节点,node将插入两个节点之间
- int find = 0;
- SNode preNode = this.head; // 前节点
- SNode currentNode = current; // 当前节点
- while (find < pos - 1 && currentNode != this.head) {
- preNode = current; // 前节点后移
- currentNode = currentNode.getNextNode(); // 当前节点后移
- find++;
- if (find < pos - 1 && currentNode != this.head) { // 未结束寻找节点前,后移前节点
- current = current.getNextNode();
- }
- }
- // System.out.println(preNode);
- // System.out.println(currentNode);
- // 2、插入节点
- preNode.setNextNode(node);
- node.setNextNode(currentNode);
- this.size++;
- } else {
- System.out.println("位置信息错误");
- flag = false;
- }
- return flag;
- }
- private void initLinkList() {
- if (size == 0) {
- this.head.setNextNode(this.head);
- }
- }
- /*
- * 指定链表的节点pos,删除对应节点。方式:找到要删除节点的前后节点,进行删除,下标从1开始
- * */
- @Override public boolean deleteNode(int pos) {
- boolean flag = false;
- SNode current = this.head.getNextNode();
- if (pos <= 0 || pos > this.size || current == this.head) {
- System.out.println("位置信息错误或链表无信息");
- } else {
- // 1、找到要删除节点的前后节点
- int find = 0;
- SNode preNode = this.head; // 前节点
- SNode nextNode = current.getNextNode(); // 后节点
- while (find < pos - 1 && nextNode != this.head) {
- preNode = current; // 前节点后移
- nextNode = nextNode.getNextNode(); // 后节点后移
- find++;
- if (find < pos - 1 && nextNode != this.head) { // 未结束找节点前,后移"前节点"
- current = current.getNextNode();
- }
- }
- // System.out.println(preNode);
- // System.out.println(nextNode);
- // 2、删除节点
- preNode.setNextNode(nextNode);
- System.gc(); // 回收删除节点
- this.size--;
- flag = true;
- }
- return flag;
- }
- /*
- * 指定链表的节点pos,修改对应节点,下标从1开始
- * */
- @Override public boolean updateNode(int pos, Map < String, Object > map) {
- boolean flag = false;
- SNode node = getNode(pos, map); // 获得相应位置pos的节点
- if (node != null) {
- String data = (String) map.get("data");
- node.setData(data);
- flag = true;
- }
- return flag;
- }
- /*
- * 找到指定链表的节点pos,下标从1开始
- * */
- @Override public SNode getNode(int pos, Map < String, Object > map) {
- SNode current = this.head.getNextNode();
- if (pos <= 0 || pos > this.size || current == this.head) {
- System.out.println("位置信息错误或链表不存在");
- return null;
- }
- int find = 0;
- while (find < pos - 1 && current != this.head) {
- current = current.getNextNode();
- find++;
- }
- return current;
- }
- /*
- * 打印链表
- * */
- @Override public void printLink() {
- int length = this.size;
- if (length == 0) {
- System.out.println("链表为空!");
- return;
- }
- SNode current = this.head.getNextNode();
- System.out.println("总共有节点数: " + length + " 个");
- int find = 0;
- while (current != this.head) {
- System.out.println("第 " + (++find) + " 个节点 :" + current);
- current = current.getNextNode();
- }
- }
- public static void main(String[] args) {
- SingleCycleLinkList scll = new SingleCycleLinkList();
- SNode node1 = new SNode("节点1");
- SNode node2 = new SNode("节点2");
- SNode node3 = new SNode("节点3");
- SNode node4 = new SNode("节点4");
- SNode node5 = new SNode("节点5");
- SNode node6 = new SNode("插入指定位置");
- // scll.insertPosNode(scll.getSize()+1, node1) ;
- // scll.insertPosNode(scll.getSize()+1, node2) ;
- // scll.insertPosNode(scll.getSize()+1, node3) ;
- // scll.insertPosNode(scll.getSize()+1, node4) ;
- // scll.insertPosNode(scll.getSize()+1, node5) ;
- scll.insertNode(node1);
- scll.insertNode(node2);
- scll.insertNode(node3);
- scll.insertNode(node4);
- scll.insertNode(node5);
- System.out.println("*******************输出链表*******************");
- scll.printLink();
- System.out.println("*******************获得指定链表节点*******************");
- int pos = 2;
- System.out.println("获取链表第 " + pos + " 个位置数据 :" + scll.getNode(pos, null));
- System.out.println("*******************向链表指定位置插入节点*******************");
- int pos1 = 3;
- System.out.println("将数据插入第" + pos1 + "个节点:");
- scll.insertPosNode(pos1, node6);
- scll.printLink();
- System.out.println("*******************删除链表指定位置节点*******************");
- int pos2 = 3;
- System.out.println("删除第" + pos2 + "个节点:");
- scll.deleteNode(pos2);
- scll.printLink();
- System.out.println("*******************修改链表指定位置节点*******************");
- int pos3 = 3;
- System.out.println("修改第" + pos3 + "个节点:");
- Map < String,
- Object > map = new HashMap < >();
- map.put("data", "this is a test");
- scll.updateNode(pos3, map);
- scll.printLink();
- }
- }
二、双链表循环链表
- package LinkListTest;
- import java.util.HashMap;
- import java.util.Map;
- public class DoubleCycleLinkList implements ICommOperate < DNode > {
- private DNode head = new DNode("HEAD"); // 公共头指针,声明之后不变
- private int size = 0; // 记录链表节点数量
- public int getSize() {
- return this.size;
- }
- /*
- * 链表插入,每次往末端插入,判定末端的标准为next是否指向head
- * */
- @Override public boolean insertNode(DNode node) {
- boolean flag = false;
- initLinkList(); // 初始化链表
- DNode current = this.head;
- if (this.size == 0) { // 空链表
- this.head.setNextNode(node);
- node.setPriorNode(this.head);
- node.setNextNode(this.head);
- } else { // 链表内节点
- while (current.getNextNode() != this.head) { // 找到末端节点
- current = current.getNextNode();
- }
- current.setNextNode(node);
- node.setPriorNode(current);
- node.setNextNode(this.head); // 循坏链表,尾节点指向head
- }
- this.size++;
- flag = true;
- return flag;
- }
- /*
- * 插入链表指定位置pos,从1开始,而pos大于size则插入链表末端
- * */
- @Override public boolean insertPosNode(int pos, DNode node) {
- boolean flag = true;
- initLinkList(); // 初始化链表
- DNode current = this.head.getNextNode();
- if (this.size == 0) { // 链表为空
- this.head.setNextNode(node);
- node.setPriorNode(this.head);
- node.setNextNode(this.head);
- this.size++;
- } else if (pos > this.size) { // pos位置大于链表长度,插入末端
- insertNode(node);
- } else if (pos > 0 && pos <= this.size) { // 链表内节点
- // 1、找到要插入位置pos节点,插入pos节点当前位置
- int find = 0;
- while (find < pos - 1 && current.getNextNode() != this.head) {
- current = current.getNextNode();
- find++;
- }
- // 2、插入节点
- if (current.getNextNode() == this.head) { // 尾节点
- node.setPriorNode(current);
- node.setNextNode(this.head);
- current.setNextNode(node);
- } else if (current.getNextNode() != this.head) { //中间节点
- node.setPriorNode(current.getPriorNode());
- node.setNextNode(current);
- current.getPriorNode().setNextNode(node);
- current.setPriorNode(node);
- }
- this.size++;
- } else {
- System.out.println("位置信息错误");
- flag = false;
- }
- return flag;
- }
- private void initLinkList() {
- if (size == 0) {
- this.head.setNextNode(this.head);
- this.head.setPriorNode(this.head);
- }
- }
- /*
- * 指定链表的节点pos,删除对应节点。方式:找到要删除节点的前后节点删除,下标从1开始
- * */
- @Override public boolean deleteNode(int pos) {
- boolean flag = false;
- DNode current = this.head.getNextNode();
- if (pos <= 0 || pos > this.size || current == this.head) {
- System.out.println("位置信息错误或链表不存在");
- } else {
- // 1、找到要删除位置pos节点
- int find = 0;
- while (find < pos - 1 && current.getNextNode() != this.head) {
- current = current.getNextNode();
- find++;
- }
- // 2、删除节点
- if (current.getNextNode() == this.head) { // 尾节点
- current.getPriorNode().setNextNode(this.head);
- } else if (current.getNextNode() != this.head) { //中间节点
- current.getPriorNode().setNextNode(current.getNextNode());
- current.getNextNode().setPriorNode(current.getPriorNode());
- }
- System.gc(); // 回收删除节点
- this.size--;
- flag = true;
- }
- return flag;
- }
- /*
- * 指定链表的节点pos,修改对应节点,下标从1开始
- * */
- @Override public boolean updateNode(int pos, Map < String, Object > map) {
- boolean flag = false;
- DNode node = getNode(pos, map);
- if (node != null) {
- String data = (String) map.get("data");
- node.setData(data);
- flag = true;
- }
- return flag;
- }
- /*
- * 找到指定链表的节点pos,下标从1开始
- * */
- @Override public DNode getNode(int pos, Map < String, Object > map) {
- DNode current = this.head.getNextNode();
- if (pos <= 0 || pos > this.size || current == this.head) {
- System.out.println("位置信息错误或链表不存在");
- return null;
- }
- int find = 0;
- while (find < pos - 1 && current != this.head) {
- current = current.getNextNode();
- find++;
- }
- return current;
- }
- /*
- * 打印链表
- * */
- @Override public void printLink() {
- int length = this.size;
- if (length == 0) {
- System.out.println("链表为空!");
- return;
- }
- DNode current = this.head.getNextNode();
- int find = 0;
- System.out.println("总共有节点数: " + length + " 个");
- while (current != this.head) {
- System.out.println("第 " + (++find) + " 个节点 :" + current);
- current = current.getNextNode();
- }
- }
- public static void main(String[] args) {
- DoubleCycleLinkList dcll = new DoubleCycleLinkList();
- DNode node1 = new DNode("节点1");
- DNode node2 = new DNode("节点2");
- DNode node3 = new DNode("节点3");
- DNode node4 = new DNode("节点4");
- DNode node5 = new DNode("节点5");
- DNode node6 = new DNode("插入指定位置");
- dcll.insertPosNode(10, node1);
- dcll.insertPosNode(10, node2);
- dcll.insertPosNode(8, node3);
- dcll.insertPosNode(88, node4);
- dcll.insertPosNode(8, node5);
- // dcll.insertNode(node1);
- // dcll.insertNode(node2);
- // dcll.insertNode(node3);
- // dcll.insertNode(node4);
- // dcll.insertNode(node5);
- System.out.println("*******************输出链表*******************");
- dcll.printLink();
- System.out.println("*******************获得指定链表节点*******************");
- int pos = 2;
- System.out.println("获取链表第 " + pos + "个位置数据 :" + dcll.getNode(pos, null));
- System.out.println("*******************向链表指定位置插入节点*******************");
- int pos1 = dcll.getSize() + 1;
- System.out.println("将数据插入第" + pos1 + "个节点:");
- dcll.insertPosNode(pos1, node6);
- dcll.printLink();
- System.out.println("*******************删除链表指定位置节点*******************");
- int pos2 = 7;
- System.out.println("删除第" + pos2 + "个节点:");
- dcll.deleteNode(pos2);
- dcll.printLink();
- System.out.println("*******************修改链表指定位置节点*******************");
- int pos3 = 3;
- System.out.println("修改第" + pos3 + "个节点:");
- Map < String,
- Object > map = new HashMap < >();
- map.put("data", "this is a test");
- dcll.updateNode(pos3, map);
- dcll.printLink();
- }
- }
来源: http://www.phperz.com/article/17/1118/359696.html