【数据结构】双端链表和双向链表

双端链表和双向链表

双端链表:

一、什么是双端链表。
链表中保存着对最后一个链节点引用的链表。
二、从头部进行插入
要对链表进行判断，如果为空则设置尾节点为新添加的节点。
三、从尾部进行插入
如果链表为空，则直接设置头结点为新添加的节点，否则设置尾节点的后一个节点为新添加节点。
四、从头部进行删除
判断头结点是否为下一个结点，如果没有则设置为结点为null。

双端链表的好处就是可以从尾结点进行添加

public class Node {
    //数据域
    public long data;
    //指针域
    public Node next;
	public Node previous;
    public Node() {

    }

    public Node(long data) {
        this.data = data;
    }

    public void display(){
        System.out.print(this.data + " ");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

基本方法:

public class FirstLastLinkList {
    //头结点
    private Node first;
    //尾结点
    private Node last;

    public FirstLastLinkList() {
        first = null;
        last = null;
    }

    /**
     * 插入一个结点，在头结点后进行插入
     */
    public void insertFirst(long value) {
        Node node = new Node(value);
        if(isEmpty()) {
            last = node;
        }
        node.next = first;
        first = node;
    }

    /**
     * 插入一个结点，从尾结点进行插入
     */
    public void insertLast(long value) {
        Node node = new Node(value);
        if(isEmpty()) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
    }

    /**
     * 删除一个结点，在头结点后进行删除
     */
    public Node deleteFirst() {
        Node tmp = first;
        if(first.next == null) {
            last = null;
        }
        first = tmp.next;
        return tmp;
    }

    /**
     * 显示方法
     */
    public void display() {
        Node current = first;
        while(current != null) {
            current.display();
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 查找方法
     */
    public Node find(long value) {
        Node current = first;
        while(current.data != value) {
            if(current.next == null) {
                return null;
            }
            current = current.next;
        }
        return current;
    }

    /**
     * 删除方法，根据数据域来进行删除
     */
    public Node delete(long value) {
        Node current = first;
        Node previous = first;
        while(current.data != value) {
            if(current.next == null) {
                return null;
            }
            previous = current;
            current = current.next;
        }

        if(current == first) {
            first = first.next;
        } else {
            previous.next = current.next;
        }
        return current;

    }

    /**
     * 判断是否为空
     */
    public boolean isEmpty() {
        return (first == 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
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

双向链表

一、什么是双向量表。

每个结点除了保存了对下一个结点的引用，同时还保存着对前一个结点的引用。

二、从头部进行插入

要对链表进行判断，如果为空则设置尾结点为新添加的节点。如果不为空，还需要设置头结点的前一个结点为新添加的结点。

三、从尾部进行插入

如果链表为空，则直接设置头结点为新添加的结点，否则设置尾结点的后一个结点为新添加节点。同时设置新添加的结点的前一个节点为尾结点。

四、从头部进行删除

判断头结点是否有下一个结点，如果没有则设置为结点为null。否则设置头结点的下一个结点为previous为null。

五、从尾部进行删除

如果头结点后没有其他节点，则设置尾节点为null。否则设置尾节点前一个结点的next为null。设置尾结点为其前一个节点。

六、删除方法。

不需要再使用一个临时的指针域。

package Study.DataStructure.FirstNodeLast;


/*
 * 双向链表
 */
public class DoubleLinkList {
	//头结点
	private Node first;
	//尾结点
	private Node last;

	public DoubleLinkList() {
		first = null;
		last = null;
	}

	/**
	 * 插入一个结点，在头结点后进行插入
	 */
	public void insertFirst(long value) {
		Node node = new Node(value);
		if(isEmpty()) {
			last = node;
		} else {
			first.previous = node;
		}
		node.next = first;
		first = node;
	}

	/**
	 * 插入一个结点，从尾结点进行插入
	 */
	public void insertLast(long value) {
		Node node = new Node(value);
		if(isEmpty()) {
			first = node;
		} else {
			last.next = node;
			node.previous = last;
		}
		last = node;
	}

	/**
	 * 删除一个结点，在头结点后进行删除
	 */
	public Node deleteFirst() {
		Node tmp = first;
		if(first.next == null) {
			last = null;
		} else {
			first.next.previous = null;
		}
		first = tmp.next;
		return tmp;
	}

	/**
	 * 删除结点，从尾部进行删除
	 */
	public Node deleteLast() {
		Node tmp = last;
		if(first.next == null) {
			first = null;
		} else {
			last.previous.next = null;
		}
		last = last.previous;
		return last;
	}

	/**
	 * 显示方法
	 */
	public void display() {
		Node current = first;
		while(current != null) {
			current.display();
			current = current.next;
		}
		System.out.println();
	}

	/**
	 * 查找方法
	 */
	public Node find(long value) {
		Node current = first;
		while(current.data != value) {
			if(current.next == null) {
				return null;
			}
			current = current.next;
		}
		return current;
	}

	/**
	 * 删除方法，根据数据域来进行删除
	 */
	public Node delete(long value) {
		Node current = first;
		while(current.data != value) {
			if(current.next == null) {
				return null;
			}
			current = current.next;
		}

		if(current == first) {
			first = first.next;
		} else {
			current.previous.next = current.next;
		}
		return current;

	}

	/**
	 * 判断是否为空
	 */
	public boolean isEmpty() {
		return (first == 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
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