单链表的遍历删除修改的实现

holistic杀手

大家好，这是一个没有用索引完成的单向链表的部分功能（删除、修改、获取全部元素）的代码。感觉用索引会好一些，因为可能存在一个元素重复存储的情况。 [/b]

1. /*
   
2. 单链表中的节点：
   
3.     节点是单向链表中的基本的单元。
   
4.     每一个节点Node都有两个属性。
   
5.         一个属性：是存储的数据。
   
6.         另一个属性：是下一个节点的内存地址。
   
7. */
   
8. public class Node<E> {
   
9.     //数据
   
10.     E element;
    
11. 
    
12.     //下一个节点的内存地址
    
13.     Node next;
    
14. 
    
15.     public Node() {
    
16.     }
    
17. 
    
18.     public Node(E element, Node next) {
    
19.         this.element = element;
    
20.         this.next = next;
    
21.     }
    
22. }
    
23. 
    
24. /*
    
25. 链表类。(单向链表)
    
26. */
    
27. public class Link<E> {
    
28.   
    
29.     //头节点
    
30.     private Node header;
    
31. 
    
32.     private int size =0;
    
33. 
    
34.     public int getSize(){
    
35.         return size;
    
36.     }
    
37. 
    
38. 
    
39.     // 向链表中添加元素的方法（向末尾添加）
    
40.     public void add(E data){
    
41.     //public void add(Object data){
    
42.         if (header == null){
    
43.             // 说明还没有节点。
    
44.             // new一个新的节点对象，作为头节点对象。
    
45.             // 这个时候的头节点既是一个头节点，又是一个末尾节点。
    
46.             header = new Node(data,null);
    
47.         }else{
    
48.             // 说明头不是空！
    
49.             // 头节点已经存在了！
    
50.             // 找出当前末尾节点，让当前末尾节点的next是新节点。
    
51.             Node currentLastNode = findLast(header);
    
52.             currentLastNode.next = new Node(data,null);
    
53.         }
    
54.         size++;
    
55.     }
    
56. 
    
57.     /**
    
58.      * 专门查找末尾节点的方法。
    
59.      * @param node 传进来的节点
    
60.      * @return     传进来的节点的next为空，返回该节点;不为空进行递归，直到找到某个节点的next为空，返回该节点。
    
61.      */
    
62.     private Node findLast(Node node) {
    
63.         // 如果一个节点的next是null
    
64.         // 说明这个节点就是末尾节点
    
65.         if (node.next==null){
    
66.             return node;
    
67.         }
    
68.         //程序能够到这里说明：node不是末尾节点。
    
69.         return findLast(node.next);//递归
    
70.     }
    
71. 
    
72.     // 删除链表中某个数据的方法****************
    
73.     public void remove(E data){
    
74.          Node node = contains(data,header);
    
75.         if (node==null){
    
76.             throw new ElementNotFoundException("ExceptionWarning:ElementNotFound！");
    
77.         }else {
    
78.             if (node==header){
    
79.                 header =node.next;
    
80.                 node.next =null;
    
81.             }else if(node==findLast(header)){
    
82.                 findprev(data,header).next=null;
    
83.             }else {
    
84.                 Node prevnode = findprev(data, header);
    
85.                 prevnode.next = node.next;
    
86.             }
    
87. 
    
88.             size--;
    
89.         
    
90.         }
    
91. 
    
92.     }
    
93. 
    
94.     /**
    
95.      * 找该节点的上一个节点
    
96.     */
    
97.     private Node findprev(E data,Node node) {
    
98.         if (node.next.element == data){
    
99.             return node;
    
100.         }
     
101.         return (findprev(data,node.next));
     
102.     }
     
103. 
     
104.     /*
     
105.     看链表中是否包含该数据
     
106.      */
     
107.     private Node contains(E data,Node node) {
     
108.         if (node.element==data){
     
109.            return node;
     
110.         }else if(node.next != null){
     
111.             return contains(data,node.next);
     
112.         }
     
113.         return null;
     
114.     }
     
115. 
     
116.     //修改链表中某个数据的方法
     
117.     public void modify(E olddata,E newdata) {
     
118.         if (contains(olddata,header)==null){
     
119.             throw new ElementNotFoundException("ExceptionWarning:ElementNotFound！");
     
120.         }else{
     
121.             contains(olddata,header).element=newdata;
     
122.         }
     
123.     }
     
124. 
     
125.     //遍历***************
     
126.     public void getAll(){
     
127.         Node node = header;
     
128.         while (node!=null){
     
129.             System.out.println(node.element);
     
130.             node=node.next;
     
131.         }
     
132. 
     
133.     }
     
134. 
     
135. 
     
136. 
     
137. }
     
138. 
     
139. class ElementNotFoundException extends RuntimeException{
     
140.     public ElementNotFoundException(){}
     
141. 
     
142.     public ElementNotFoundException(String s){
     
143.         super(s);
     
144.     }
     
145. }
     

复制代码