双端链表
对于单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多。
1、什么时双端链表：
链表中保持这对最后一个连点引用的链表
2、从头部插入
要对链表进行判断，如果为空则设置尾节点为新添加的节点
3、从尾部进行插入
如果链表为空，则直接设置头节点为新添加的节点，否则设置尾节点的后一个节点为新添加的节点
4、从头部删除
判断节点是否有下个节点，如果没有则设置节点为null
/**
* @Auther: liuhaidong
* Data: 2019/10/11 0011、12:07
* Description:
* @version: 1.0
*/
public class DoublePointLinkedList {
private Node head;
//头节点
private Node tail;
//尾节点
private int size;
//节点的个数
public DoublePointLinkedList() {
size = 0;
head = null;
tail = null;
}
//表头新增节点
public void addHead(int data){
Node node = new Node(data);
if (size == 0) {
//如果链表为空，那么头节点和尾节点都是该新增节点
head = node;
tail = node;
size++;
} else {
node.next = head;
head = node;
size++;
}
}
//链表尾新增节点
public void addTail(int data) {
Node node = new Node(data);
if (size == 0) {
//如果链表为空，那么头节点和尾节点都是该新增节点
head = node;
tail = node;
size++;
} else {
tail.next = node;
tail = node;
size++;
}
}
//删除头部节点，成功返回true，失败返回false
public boolean deleteHead() {
if (size == 0) {
//当前链表节点数为0
return false;
}
if (head.next == null) {
//当前链表节点数为1
head = null;
tail = null;
} else {
head = head.next;
}
size--;
return true;
}
/**
* @Author liuhaidong
* @Description 显示出所有的节点信息(已测试)
* @param
* @Date 10:55 2019/10/11 0011
*/
public void displayNode(){
if(size > 0){
Node node = head;
int tempSize = size;
if(tempSize == 1){
//当前链表只有一个节点
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else {
System.out.print(node.data + "->");
}
node = node.next;
tempSize--;
}
}
}
/**
* @Author liuhaidong
* @Description 判断链表是否为空(已测试)
* @param
* @Date 10:27 2019/10/11 0011
*/
public boolean isEmpty(){
return (size == 0);
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
}
用双端链表实现队列
/**
* @Auther: liuhaidong
* Data: 2019/10/11 0011、12:31
* Description:
* @version: 1.0
*/
public class MyQueue {
private DoublePointLinkedList dp;
/** Initialize your data structure here. */
public MyQueue() {
dp = new DoublePointLinkedList();
}
/** Push element x to the back of queue. */
public void push(int data) {
dp.addTail(data);
dp.setSize(dp.getSize()+1);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
dp.deleteHead();
//队尾元素
dp.setSize(dp.getSize()-1);
return dp.findNde(dp.getSize()).data;
}
/** Get the front element. */
public int peek() {
return dp.findNde(dp.getSize()).data;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return dp.isEmpty();
}
}
双向链表
我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。
/**
* @Auther: liuhaidong
* Data: 2019/10/11 0011、21:12
* Description:
* @version: 1.0
*/
public class TwoWayLinkedList {
private NodeTwo head;
//表示链表头
private NodeTwo tail;
//表示链表尾
private int size;
// 表示链表的节点个数
public TwoWayLinkedList() {
size = 0;
head = null;
tail = null;
}
//在链表头增加节点
public void addHead(int value) {
NodeTwo newNode = new NodeTwo(value);
if (size == 0) {
head = newNode;
tail = newNode;
size++;
} else {
head.prev = newNode;//把新的结点给原来头的前面
newNode.next = head;//旧的头结点为新的后面
head = newNode;//新的为新的结点
size++;
}
}
//在链表尾增加节点
public void addTail(int value){
NodeTwo newNode = new NodeTwo(value);
if (size == 0) {
head = newNode;
tail = newNode;
size++;
} else {
newNode.prev = tail;//原来的尾结点为新加的前面结点
tail.next = newNode;//新的结点为尾结点的下一个
tail = newNode;//新的结点为尾结点
size++;
}
}
//删除表头 并且返回
public NodeTwo deleteHead(){
NodeTwo tmp = head;
if(size != 0){
head = head.next;
head.prev = null;
size--;
}
return tmp;
}
//删除链表尾
public NodeTwo deleteTail(){
NodeTwo temp = tail;
if(size != 0){
tail = tail.prev;
tail.next = null;
size--;
}
return temp;
}
//获得链表的节点个数
public int getSize() {
return size;
}
//判断链表是否为空
public boolean isEmpty() {
return (size == 0);
}
/**
* @Author liuhaidong
* @Description 显示出所有的节点信息(已测试)
* @param
* @Date 10:55 2019/10/11 0011
*/
public void displayNode(){
if(size > 0){
NodeTwo node = head;
int tempSize = size;
if(tempSize == 1){
//当前链表只有一个节点
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else {
System.out.print(node.data + "->");
}
node = node.next;
tempSize--;
}
}
}
}
/**
* @Auther: liuhaidong
* Data: 2019/10/11 0011、21:13
* Description:
* @version: 1.0
*/
public class NodeTwo {
public int data;
public NodeTwo next;
public NodeTwo prev;
public NodeTwo(int data) {
this.data = data;
}
}
京公网安备 11010502036488号