Java模擬單向鏈表和雙向鏈表的實現

下面演示的Java模擬的單向鏈表的實現

1. package com.jadyer.sort;
3. /**
4. * 模擬單向鏈表
5. * @author 宏宇
6. * @editor Jan 23, 2012 7:55:21 PM
7. * @see ==================================================================================================
8. * @see 【數據結構的分類：線性數據結構和非線性數據結構】
9. * @see 1)線性數據結構，包含：線性表、棧、隊列、串、數組、文件
10. * @see 2)非線性數據結構，含：樹、圖
11. * @see ==================================================================================================
12. * @see 【線性表的概述：其數據元素呈線性關系】
13. * @see 1)線性表中的所有數據元素在同一個線性表中必須是相同的數據類型
14. * @see 2)線性表中必存在唯一的稱為"第一個"的數據元素，必存在唯一的稱為"最後一個"的數據元素
15. * @see 3)線性表中除第一個元素外，每個元素都有且只有一個前驅元素。除最後一個元素外，每個元素都有且只有一個後繼元素
16. * @see 4)線性表的邏輯結構是n個數據元素的有限序列(a1,a2,a3,...,an)，其中n為線性表的長度(n>=0)，n=0的表稱為空表
17. * @see ==================================================================================================
18. * @see 【線性表的分類：按其存儲結構可分為順序表和鏈表】
19. * @see 1)順序表：用順序存儲結構存儲的線性表稱為順序表。即內存地址中的元素是按照循序連續存放的
20. * @see 也可以說，將線性表中的數據元素依次存放在某個存儲區域中，所形成的表稱為順序表
21. * @see 一維數組就是用順序方式存儲的線性表，所以ArrayList可以看作是一種順序表
22. * @see 2)鏈表：用鏈式存儲結構存儲的線性表稱為鏈表。即內存地址中的元素不是連續存放的
23. * @see ==================================================================================================
24. * @see 【stack】
25. * @see 棧(stack)也是一種特殊的線性表，是限定僅在表尾進行插入和刪除運算的線性表
26. * @see 棧的物理存儲可以用順序存儲結構，也可以用鏈式存儲結構
27. * @see 棧是一種後進先出(LIFO)的結構，棧的表尾稱為棧頂(top)，棧的表頭稱為棧底(bottom)
28. * @see ==================================================================================================
29. * @see 【Queue】
30. * @see 隊列(Queue)是限定所有的插入只能在表的一端進行，而所有的刪除都在表的另一端進行的線性表
31. * @see 隊列的物理存儲可以用順序存儲結構，也可以用鏈式存儲結構
32. * @see 隊列是一種先進先出(FIFO)的結構，其中允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊頭(Front)(有點像等公交車)
33. * @see ==================================================================================================
34. */
35. class NodeOneWay {
36. String data; //存放節點數據本身
37. NodeOneWay next; //存放指向後一個節點的引用
39. public NodeOneWay(){}
41. public NodeOneWay(String data){
42. this.data = data;
43. }
44. }
47. /**
48. * 單向鏈表測試類
49. * @author 宏宇
50. * @editor Jan 23, 2012 7:56:51 PM
51. */
52. public class NodeOneWayTest {
53. public static void main(String[] args) {
54. NodeOneWay node11 = new NodeOneWay("node11_data");
55. NodeOneWay node22 = new NodeOneWay("node22_data");
56. NodeOneWay node33 = new NodeOneWay("node33_data");
57. node11.next = node22; //生成後繼關系
58. node22.next = node33;
59. System.out.println(node11.next.next.data); //通過node11獲得node33的data屬性值
60. /**
61. * 生成node44對象，並將其插入到node11和node22中間
62. */
63. NodeOneWay node44 = new NodeOneWay("node44_data");
64. node11.next = node44; //修改node11的後繼關系指向node44
65. node44.next = node22; //修改node44的後繼關系指向node22
66. System.out.println(node11.next.next.next.data); //通過node11獲得node33的data屬性值
67. System.out.println(node11.next.next.data); //通過node11獲得node22的data屬性值
68. /**
69. * 刪除node44對象
70. */
71. node11.next = node22; //即node11的後繼關系指向node22，node44的後繼關系不再指向node22
72. node44.next = null;
73. System.out.println(node11.next.next.data); //通過node11獲得node33的data屬性值
74. }
75. }