tosser 阅读(8) 评论(0)

  链表是一种常见的基础数据结构,它是一种线性表,但在内存中它并不是顺序存储的,它是以链式进行存储的,每一个节点里存放的是下一个节点的“指针”。在Java中的数据分为引用数据类型和基础数据类型,在Java中不存在指针的概念,但是对于链表而言的指针,指的就是引用数据类型的地址。

 

  链表和数组都是线性的数据结构,对于数组而言其长度是固定的,由于在内存中其是连续的,因此更适合做查找与遍历,而链表在内存中是并不是顺序存储的,但是由于其是通过“指针”构成的,因此在插入、删除时比较数组更为的方便。

 

  下面的代码通过内部类并结合递归的方式来实现了一个简单的用Java语言描述的链表的数据结构。

 

  首先来看一下,链表数据结构的定义,代码如下:

 1 class NodeManager {
 2     private Node root;      // 根节点
 3     private int currentIndex = 0;   // 节点的序号,每次操作从0开始
 4     
 5     public void add(int data) {}
 6     public void delNode(int data) {}
 7     
 8     public void print() {}
 9     
10     public boolean findNode(int data) {}
11     
12     public boolean updateNode(int oldData, int newData) {}
13     
14     // 向索引之前插入
15     public void insert(int index, int data) {}
16     
17     // 谁拥有数据,谁提供方法
18     class Node {
19         private int data;
20         private Node next;  // 把当前类型作为属性
21         
22         public Node(int data) {
23             this.data = data;
24         }
25         
26         public void setData(int data) {
27             this.data = data;
28         }
29         
30         public int getData() {
31             return data;
32         }
33         
34         // 添加节点
35         public void addNode(int data) {}
36         
37         // 删除节点
38         public void delNode(int data) {}
39         
40         // 输出所有节点
41         public void printNode() {}
42         
43         // 查找节点是否存在
44         public boolean findNode(int data) {}
45         
46         // 修改节点
47         public boolean updateNode(int oldData, int newData) {}
48         
49         // 插入节点
50         public void insertNode(int index, int data) {}
51     }
52 }

  对于链表的定义来说,NodeManager类是用来管理链表操作的,而成员内部类Node是用于提供链表数据与链式结构的。对于类的使用者来说,并不直接访问数据,因此操作的是NodeManager类,而内部类Node提供了真正的数据管理,因此Node类需要提供真正的数据操作方法,对于NodeManager类中也需要提供一套由外部来操作链表的方法。因此,在NodeManager类和Node类中都提供了看似相同的方法,但实际的意义并不相同。

  下面来查看NodeManager类和Node类中的add()方法,代码如下:

 1 public void add(int data) {
 2     if ( root == null ) {
 3         root = new Node(data);
 4     } else {
 5         root.addNode(data);
 6     }
 7 }
 8 
 9 // 添加节点
10 public void addNode(int data) {
11     if ( this.next == null ) {
12         this.next = new Node(data);
13     } else {
14         this.next.addNode(data);
15     }
16 }

  代码中上面的方法是NodeManager类中的方法,而下面的方法是Node类中的方法。

  在Manager类中提供了一个root的成员变量,它用于管理链表的头节点,因此在添加节点时,会先判断root是否为空,如果为空则直接将节点由root来进行保存,如果root不为空,则通过Node类中的addNode()方法来进行添加,添加到思路是找到当前链表的最后一个节点,并将新添加到节点赋值给最后一个节点的next成员变量中。

  对于链表的其他操作也是相同的思路,关于链表增删改查和输出的完整代码如下:

  1 class NodeManager {
  2     private Node root;      // 根节点
  3     private int currentIndex = 0;   // 节点的序号,每次操作从0开始
  4     
  5     public void add(int data) {
  6         if ( root == null ) {
  7             root = new Node(data);
  8         } else {
  9             root.addNode(data);
 10         }
 11     }
 12     public void delNode(int data) {
 13         if ( root == null ) return ;
 14         if ( root.getData() == data ) {
 15             Node tmp = root;
 16             root = root.next;
 17             tmp = null;
 18         } else {
 19             root.delNode(data);
 20         }
 21     }
 22     
 23     public void print() {
 24         if ( root != null ) {
 25             System.out.print(root.getData() + " ");
 26             root.printNode();
 27             System.out.println();
 28         }
 29     }
 30     
 31     public boolean findNode(int data) {
 32         if ( root == null ) return false;
 33         if ( root.getData() == data ) {
 34             return true;
 35         } else {
 36             return root.findNode(data);
 37         }        
 38     }
 39     
 40     public boolean updateNode(int oldData, int newData) {
 41         if ( root == null ) return false;
 42         if ( root.getData() == oldData ) {
 43             root.setData(newData);
 44             return true;
 45         } else {
 46             return root.updateNode(oldData, newData);
 47         }
 48     }
 49     
 50     // 向索引之前插入
 51     public void insert(int index, int data) {
 52         if ( index < 0 ) return ;
 53         currentIndex = 0;
 54         if ( index == currentIndex ) {
 55             Node newNode = new Node(data);
 56             newNode.next = root;
 57             root = newNode;
 58         } else {
 59             root.insertNode(index, data);
 60         }
 61     }
 62     
 63     // 谁拥有数据,谁提供方法
 64     class Node {
 65         private int data;
 66         private Node next;  // 把当前类型作为属性
 67         
 68         public Node(int data) {
 69             this.data = data;
 70         }
 71         
 72         public void setData(int data) {
 73             this.data = data;
 74         }
 75         
 76         public int getData() {
 77             return data;
 78         }
 79         
 80         // 添加节点
 81         public void addNode(int data) {
 82             if ( this.next == null ) {
 83                 this.next = new Node(data);
 84             } else {
 85                 this.next.addNode(data);
 86             }
 87         }
 88         
 89         // 删除节点
 90         public void delNode(int data) {
 91             if ( this.next != null ) {
 92                 if ( this.next.getData() == data ) {
 93                     Node tmp = this.next;
 94                     this.next = this.next.next;
 95                     tmp = null;
 96                 } else {
 97                     this.next.delNode(data);
 98                 }
 99             }
100         }
101         
102         // 输出所有节点
103         public void printNode() {
104             if ( this.next != null ) {
105                 System.out.print(this.next.getData() + " ");
106                 this.next.printNode();
107             }
108         }
109         
110         // 查找节点是否存在
111         public boolean findNode(int data) {
112             if ( this.next != null ) {
113                 if ( this.next.getData() == data ) {
114                     return true;
115                 } else {
116                     return this.next.findNode(data);
117                 }
118             }
119             
120             return false;
121         }
122         
123         // 修改节点
124         public boolean updateNode(int oldData, int newData) {
125             if ( this.next != null ) {
126                 if ( this.next.getData() == oldData ) {
127                     this.next.setData(newData);
128                     return true;
129                 } else {
130                     return this.next.updateNode(oldData, newData);
131                 }
132             }
133             return false;
134         }
135         
136         // 插入节点
137         public void insertNode(int index, int data) {
138             currentIndex ++;
139             if ( index == currentIndex ) {
140                 Node newNode = new Node(data);
141                 newNode.next = this.next;
142                 this.next = newNode;
143             } else {
144                 this.next.insertNode(index, data);
145             }
146         }
147     }
148 }

  以上就是链表基本操作的完整代码,下面写一个调用的代码进行测试,代码如下:

 1 public class LinkList {
 2     public static void main(String[] args) {
 3         NodeManager nm = new NodeManager();
 4         System.out.println("链表的添加(添加5、4、3、2、1)");
 5         nm.add(5);
 6         nm.add(4);
 7         nm.add(3);
 8         nm.add(2);
 9         nm.add(1);
10         nm.print();
11         System.out.println("链表的删除(删除3)");
12         nm.delNode(3);
13         nm.print();
14         System.out.println("链表的查找(查找1)");
15         System.out.println(nm.findNode(1));
16         System.out.println("链表的查找(查找10)");
17         System.out.println(nm.findNode(10));
18         System.out.println("链表的更新(把1更新为10)");
19         nm.updateNode(1, 10);
20         nm.print();
21         System.out.println("链表的插入(在第1个位置插入20)");
22         nm.insert(1, 20);
23         nm.print();
24         System.out.println("链表的插入(在第0个位置插入30)");
25         nm.insert(0, 30);
26         nm.print();
27     }
28 }

  将代码编译、运行,结果如下图:

 

  对于Java中的集合类中用到了不少的数据结构的知识,等自己状态好的时候学习学习Java集合类的源码。我会努力做一个初级程序员!