首页 > 代码库 > Singly Link List(单链表的实现java)

Singly Link List(单链表的实现java)

2024-07-06 08:07:05   226人阅读

?
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
package com.datastructure.singlylinklist;
/**
 * 实现一个单链表
 * 实现功能：
 * 增加一个节点（头插法，尾插法）
 * 删除一个节点（删除第一个节点，删除最后一个节点，删除任何一个节点）
 * 查找（查找到一个list中的某个元素）
 * @author Xinyuyu
 *
 */
public class SinglyLinkList <T> {
    /*
     * 实现一个节点的数据结构
     * 数据域
     * 指针域
     */
    // header指向list的头
    // tail指向list的尾
    private IntSLLNode header;
    private IntSLLNode tail;
    class IntSLLNode{
        public Object data;
        public IntSLLNode next;
        //
        public IntSLLNode(Object data){
            this(data, null);
        }
 
        public IntSLLNode(Object data, IntSLLNode next){
            this.data = http://www.mamicode.com/data;
            this.next = next;
        }
    }
     
    public SinglyLinkList(){
        header = tail = null;
    }
 
    // 头插法增加一个节点
    public void addToHeader(Object o){
        // 链表不为空的情况
        // 链表为空的情况
        header = new IntSLLNode(o, header);
        if(tail == null)
            tail = header;
    }
    // 尾插法增加一个节点
    public void addToTail(Object o){
        // 链表不为空的情况
        // 链表为空的情况
        IntSLLNode newNode = new IntSLLNode(o);
        if(!isEmpty()){
            tail.next = newNode;
            tail = newNode;
        }else
            tail = header = newNode;
    }
    // 删除第一个节点
    public Object deleteFromHeader() throws Exception{
        // 链表不为空切大于一个节点
        // 链表仅有一个节点
        // 链表为空
        IntSLLNode node = header;
        if(!isEmpty()){
            header = header.next;
        }else if(!isEmpty() && header == tail){
            tail = header = null;
        }else{
            // 链表为空抛出异常
            throw new Exception("SSL is empty");
        }
         
        return node.data;
    }
    // 删除最后一个节点
    public Object delteFromTail() throws Exception{
        // 链表不是空且大于一个节点的时候
        // 链表仅有一个节点的时候
        // 链表是空的情况
        IntSLLNode node = tail;
        if(!isEmpty() && header != tail){
            // 一个临时指针，指向头节点，遍历到倒数第二个节点出，将尾指针指向倒数第二个节点
            IntSLLNode temp = header;
            for(; temp.next != tail;){
                temp = temp.next;
            }
            tail = temp;
            temp.next = null;
        }else if(!isEmpty() && header == tail){
            tail = header  = null;
        }else{
            // 当列表为空的时候抛出异常
            throw new Exception("SSL is empty");
        }
        return node.data;
    }
    // 删除链表中的某个节点
    public Object delete(Object o) throws Exception{
        // 链表不为空且包含大于一个节点
        // 链表仅包含一个节点
        // 链表为空的情况
         
        // 删除的为第一个节点
        if(o.equals(header.data)){
            return deleteFromHeader();
            // 删除的为最后一个节点
        }else if(o.equals(tail.data)){
            return delteFromTail();
        }else{
            IntSLLNode temp = header;
            if(!isEmpty() && header != tail){
                for(; !temp.next.data.equals(o);){
                     temp = temp.next;
                }
                if(temp != null){
                    temp.next = temp.next.next;
                    temp = temp.next;
                }
            }else if(!isEmpty() && header == tail){
                if(header.equals(o)){
                    temp = header;
                    header = tail = null;
                }
            }else{
                throw new Exception("SSL is empty");
            }
            return temp.data;
        }
        // 如果查找到就返回一个节点信息
        // 查找不到
    }
    // 删除节点的另外一个写法(需要两个指针)
    public Object deletePro(Object o) throws Exception{
        // 链表不为空且大于一个节点
        // 链表仅包含一个节点
        // 链表为空
        IntSLLNode node = null;
        if(header.data.equals(o)){
            return deleteFromHeader();
        }
        if(!isEmpty() && header != tail){
            IntSLLNode pre = header, las = header.next;
            for(; las != null && !las.data.equals(o); ){
                pre = pre.next;
                las = las.next;
            }
            if(las != null)
                pre.next = las.next;
            else
                return delteFromTail();
            node = las;
        }else if(!isEmpty() && header == tail){
            if(header.equals(o));
                tail = header = null;
        }else{
            throw new Exception("SSL is empty");
        }
        return node.data;
    }
    // 查找链表中的某个节点
    public Object find(Object o) throws Exception{
        // 链表为空
        // 链表不为空
        IntSLLNode temp = null;
        if(!isEmpty()){
            temp = header;
            for(; temp != null && !temp.data.equals(o); ){
                temp = temp.next;
            }
            if(temp == null)
                return null;
            else
                return temp.data;
        }else{
            // 当链表为空的时候也就是不会查找到需要的节点
            throw new Exception("The object is not exist in the SLL");
        }
    }
     
    // 判断链表是否为空
    public boolean isEmpty(){
        return header == null;
    }
     
    // 打印出链表
    public void printSinglyLinkList(String name){
        System.out.print(name + " : ");
        for(IntSLLNode tempNode = header; tempNode != null; tempNode = tempNode.next){
            System.out.print(tempNode.data.toString() + "->");
        }
    }
    // 清空列表
    public void emptySLL(){
        header = tail = null;
    }
}
?
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
package SinglyLinkList;
 
public class Persion {
    private String name;
    private int age;
     
    public Persion(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
     
    public String toString(){
        return "[" + this.name + " age is " + this.age + "]";
    }
    // 需要重写equal方法来完成删除和查找
    @Override
    public boolean equals(Object o) {
        if(this.name.equals(((Persion) o).getName()) && this.age == ((Persion) o).getAge())
            return true;
        else
            return false;
    }
}

 

?
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
package SinglyLinkList;
 
import com.datastructure.singlylinklist.SinglyLinkList;
 
public class TestOfSinglyList {
    public static void main(String[] args) {
        SinglyLinkList<Persion> singlyLinkList = new SinglyLinkList<Persion>();
        Persion p1 = new Persion("张三", 34);
        Persion p2 = new Persion("李四", 24);
        Persion p3 = new Persion("王五", 44);
        Persion p4 = new Persion("李以", 44);
        Persion p5 = new Persion("王七", 44);
         
        // 完成头插法
        singlyLinkList.addToHeader(p1);
        singlyLinkList.addToHeader(p2);
        singlyLinkList.addToHeader(p3);
        singlyLinkList.addToHeader(p4);
        singlyLinkList.addToHeader(p5);
         
        singlyLinkList.printSinglyLinkList("完成头插法");
        System.out.println();
//      System.out.println();
//      // 清空链表
//      singlyLinkList.emptySLL();
//      // 完成尾插法
//      singlyLinkList.addToTail(p1);
//      singlyLinkList.addToTail(p2);
//      singlyLinkList.addToTail(p3);
//      singlyLinkList.printSinglyLinkList("完成头插法");
//      System.out.println();
//      // 完成删除尾节点
//      try {
//          Persion p = (Persion)singlyLinkList.delteFromTail();
//          singlyLinkList.printSinglyLinkList("删除了最后一个节点");
//          System.out.println();
//          System.out.println("被删除的尾节点是 :" + p.getName() + " age is " + p.getAge());
//      } catch (Exception e) {
//          e.printStackTrace();
//      }
//      // 完成删除头节点
//      try {
//          Persion p = (Persion)singlyLinkList.deleteFromHeader();
//          singlyLinkList.printSinglyLinkList("删除了第一个节点");
//          System.out.println();
//          System.out.println("被删除的头节点是 :" + p.getName() + " age is " + p.getAge());
//      } catch (Exception e) {
//          e.printStackTrace();
//      }
        // 删除任意一个节点
        //Persion p = new Persion("张三", 34);
        try {
            singlyLinkList.deletePro(p5);
            singlyLinkList.deletePro(p4);
            singlyLinkList.deletePro(p3);
            singlyLinkList.deletePro(p2);
            singlyLinkList.deletePro(p1);
             
             
        } catch (Exception e) {
            e.printStackTrace();
        }
        singlyLinkList.printSinglyLinkList("任意删除一个节点");
        System.out.println();
        try {
            System.out.println(singlyLinkList.find(p1));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

 


联系
我们