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

双端链表和双向链表

双端链表:

一、什么是双端链表。
链表中保存着对最后一个链节点引用的链表。
二、从头部进行插入
要对链表进行判断,如果为空则设置尾节点为新添加的节点。
三、从尾部进行插入
如果链表为空,则直接设置头结点为新添加的节点,否则设置尾节点的后一个节点为新添加节点。
四、从头部进行删除
判断头结点是否为下一个结点,如果没有则设置为结点为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 + " ");
    }
}

基本方法:

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);
    }
}

双向链表

一、什么是双向量表。

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

二、从头部进行插入

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

三、从尾部进行插入

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

四、从头部进行删除

判断头结点是否有下一个结点,如果没有则设置为结点为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);
	}
}

    原文作者:evan_qb
    原文地址: https://blog.csdn.net/Evan_QB/article/details/83964090
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞