服务器之家

服务器之家 > 正文

java数据结构基础:单链表与双向链表

时间:2021-11-01 11:06     来源/作者:去吧猫头夜鹰

单链表:

每个数据是以节点的形式存在的

每个节点分为数据域和指针域

数据域中保存该节点的数据

指针域中保存指向下一个节点的指针

实现思路:

节点类SingleNode中保存数据和指向下一个节点的指针

单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法

对于链表方法,涉及到位置查找,如在指定位置增加、删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置。

对于节点的增加删除,只需要修改相关结点的指针指向即可

代码实现:

节点类SingleNode:

?
1
2
3
4
5
6
7
8
9
10
11
public class SingleNode {
    public int data;
    public SingleNode next;
    public SingleNode(int data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "SingleNode{" + "data=" + data + '}';
    }
}

单链表类SingleLinkedList

?
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
public class SingleLinkedList {
    private SingleNode head = new SingleNode(0);
    //获取头结点
    public SingleNode getHead(){
        return head;
    }
    //添加节点
    public void add(SingleNode singleNode) {
        SingleNode temp = head;
        //找到链表最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = singleNode;
    }
    //按顺序添加节点
    public void addByOrder(SingleNode singleNode) {
        SingleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //已经遍历到链表最后了
                break;
            } else if (temp.next.data > singleNode.data) {
                //找到应插入的位置
                break;
            }
            temp = temp.next;
        }
        singleNode.next = temp.next;
        temp.next = singleNode;
    }
    //删除节点
    public void delete(int data) {
        SingleNode temp = head;
        boolean flag = false;    //标志是否找到待删除节点的前一个节点
        while (true) {
            if (temp.next == null) {
                //已经遍历到链表最后了
                break;
            } else if (temp.next.data == data) {
                //找到待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("要删除的节点不存在");
        }
    }
    //输出链表
    public void show() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        SingleNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

双向链表:

每个节点中除了保存了指向后一个节点的指针外,还保存了指向前一个节点的指针

实现思路:

相关方法实现与单链表类似,不同点在于需要增加对指向前一个节点的指针的更改

代码实现:

节点类DoubleNode:

?
1
2
3
4
5
6
7
8
9
10
11
12
public class DoubleNode {
    public int data;
    public DoubleNode next;
    public DoubleNode pre;
    public DoubleNode(int data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "DoubleNode{" + "data=" + data + '}';
    }
}

双向链表类DoubleLinkedList:

?
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
public class DoubleLinkedList {
    public DoubleNode head = new DoubleNode(0);
    //获取头结点
    public DoubleNode getHead() {
        return head;
    }
    //添加节点
    public void add(DoubleNode doubleNode) {
        DoubleNode temp = head;
        //找到链表最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = doubleNode;
        doubleNode.pre = temp;
    }
    //删除节点
    public void delete(int data) {
        DoubleNode temp = head.next;
        boolean flag = false;    //标志是否找到待删除节点的前一个节点
        while (true) {
            if (temp == null) {
                //已经遍历到链表最后了
                break;
            } else if (temp.data == data) {
                //找到待删除节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null) {
                //若删除节点不为最后一个节点
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.println("要删除的节点不存在");
        }
    }
    //输出链表
    public void show() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        DoubleNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/qq_25274377/article/details/119246506

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部