java 实现双向链表实例详解

java 实现双向链表实例详解

java 实现双向链表实例详解

双向链表是一个基本的数据结构，在Java中LinkedList已经实现了这种结构，不过作为开发者，也要拥有自己显示这种结构的能力。话不多说，上代码：

首先是链表的节点类：

/**

* 链表节点

* @author Administrator

*

* @param

*/

public class ChainNode {

private T data;

//对象编号

private int dataNo;

public ChainNode nextChainNode;

public ChainNode preChainNode;

public ChainNode(T data, ChainNode nextChainNode,

ChainNode preChainNode) {

this.data = data;

this.nextChainNode = nextChainNode;

this.preChainNode = preChainNode;

}

public ChainNode(T data) {

this.data = data;

}

public int getDataNo() {

return dataNo;

}

public void setDataNo(int dataNo) {

this.dataNo = dataNo;

}

public void setData(T data) {

this.data = data;

}

public T getData() {

return data;

}

}

然后是链表：

* 链表实现类

* @author Administrator

*

* @param

*/

public class Chain {

//头节点

private ChainNode headNode;

//末尾节点指针

private ChainNode lastNode;

private int size;

//创建链表就创建头节点

public Chain() {

this.iCKhZheadNode = new ChainNode(null);

this.lastNode = headNode;

}

//增加一个节点

public void addNode(T data) {

ChainNode node = new ChainNode(data);

if(lastNode != null){

lastNode.nextChainNode = node;

node.preChainNode = node;

node.setDataNo(size);

lastNode = node;

size++;

}

}

//删除指定索引的节点

public void deleteNode(int dataNo) throws Exception {

if(getSize() == 0){

throw new Exception("chain is empty");

}

for (ChainNode node = headNode.nextChainNode;node != null;node = node.nextChainNode) {

if(node.getDataNo() == dataNo){

node.preChainNode.nextChainNode = node.nextChainNode;

if(node.nextChainNode != null){

node.nextChainNode.preChainNode = node.preChainNode;

}

node.nextChainNode = null;

node.preChainNode = null;

size--;

//重新设置节点的编号

for (ChainNode chainNode = node.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {

chainNode.setDataNo(chainNode.giCKhZetDataNo()-1);

}

return;

}

}

throw new Exception("the corresponding data that can not be found");

}

//获取指定索引的节点

public T get(int dataNo) throws Exception {

if(getSize() == 0){

throw new Exception("chain is empty");

}

for (ChainNode node = headNode.nextChainNode;node != null;node = node.nextChainNode) {

if(node.getDataNo() == dataNo){

return node.getData();

}

}

throw new Exception("the corresponding data that can not be found");

}

//修改对应索引的节点

public void set(int dataNo,T data) throws Exception {

if(getSize() == 0){

throw new Exception("chain is empty");

}

for (ChainNode node = headNode.nextChainNode;node != null;node = node.nextChainNode) {

if(node.getDataNo() == dataNo){

node.setData(data);

return;

}

}

throw new Exception("the data that is to be modified can not be found");

}

//是否包含对应数据的节点

public boolean isContains(T data) throws Exception {

if(getSize() == 0){

throw new Exception("chain is empty");

}

for (ChainNode chainNode = headNode.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {

if(chainNode.getData() == data){

return true;

}

}

return false;

}

//获取节点数量（不含头节点）

public int getSize() {

return size;

}

}

测试一下：

public class ChainTest {

public static void main(String[] args) throws Exception{

String oneString = "one";

String twoString = "two";

String threeString = "three";

String fourString = "four";

Chain chain = new Chain();

chain.addNode(oneString);

chain.addNode(twoString);

chain.addNode(threeString);

chain.addNode(fourString);

for (int i = 0; i < chain.getSize(); i++) {

String string2 = chain.get(i);

System.out.println(string2);

}

try {

String string = chain.get(2);

System.out.println("the data of the second node is"+string);

System.out.println(chain.isContains(fourString));

chain.set(1, "haha");

System.out.println("modify chain");

for (int i = 0; i < chain.getSize(); i++) {

String string2 = chain.get(i);

System.out.println(string2);

}

chain.deleteNode(3);

System.out.println("delete one node");

for (int i = 0; i < chain.getSize(); i++) {

String string2 = chain.get(i);

System.out.println(string2);

}

} catch (Exception e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

}

}

结果：

one

two

three

four

the data of the second node isthree

true

modify chain

one

haha

three

four

delete one node

one

haha

three

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。