服务器之家

服务器之家 > 正文

java 实现双向链表实例详解

时间:2020-09-02 09:55     来源/作者:Java教程网

java 实现双向链表实例详解

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

    首先是链表的节点类:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 链表节点
 * @author Administrator
 *
 * @param <T>
 */
public class ChainNode<T> {
 private T data;
 //对象编号
 private int dataNo;
  
 public ChainNode<T> nextChainNode;
 public ChainNode<T> preChainNode;
 public ChainNode(T data, ChainNode<T> nextChainNode,
   ChainNode<T> 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;
 }
  
  
}

 然后是链表:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
<pre name="code" class="java">/**
 * 链表实现类
 * @author Administrator
 *
 * @param <T>
 */
public class Chain<T> {
 //头节点
 private ChainNode<T> headNode;
 //末尾节点指针
 private ChainNode<T> lastNode;
 private int size;
  
  
 //创建链表就创建头节点
 public Chain() {
  this.headNode = new ChainNode<T>(null);
  this.lastNode = headNode;
   
 }
 //增加一个节点
 public void addNode(T data) {
  ChainNode<T> node = new ChainNode<T>(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<T> 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<T> chainNode = node.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {
     chainNode.setDataNo(chainNode.getDataNo()-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<T> 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<T> 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<T> chainNode = headNode.nextChainNode;chainNode != null;chainNode = chainNode.nextChainNode) {
   if(chainNode.getData() == data){
    return true;
   }
  }
   
  return false;
 }
 //获取节点数量(不含头节点)
 public int getSize() {
  return size;
 }
}

测试一下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class ChainTest {
 public static void main(String[] args) throws Exception{
  String oneString = "one";
  String twoString = "two";
  String threeString = "three";
  String fourString = "four";
  Chain<String> chain = new Chain<String>();
  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();
  }
 }
}

结果:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
one
two
three
four
the data of the second node isthree
true
modify chain
one
haha
three
four
delete one node
one
haha
three

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

原文链接:http://blog.csdn.net/sinat_23092639/article/details/51160621

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
iPhone12什么时候上市 iPhone12手机真实图片 苹果iphone12多少钱
iPhone12什么时候上市 iPhone12手机真实图片 苹果iphone12多少钱 2020-06-03
返回顶部