双端链表的基本操作

约定不等于承诺〃 2022-05-18 03:39 226阅读 0赞

**双端链表**：双端链表和单向链表大体上是一样的，不同的是，单向链表在表尾部分插入元素时，需要从头结点一直遍历到尾结点才能进行插入操作，这样难免有些繁琐。因此如果加入一个对尾结点的引用，这样就可以很方便地在尾结点进行插入操作，这就是双端链表。除了有一个头结点（head），还有一个尾结点（tail）。

注意它和双向链表的区别！

双端链表的Java代码实现：

package parking;
    
    
    class Node {
    
    	Object data;
    	Node next;
    
    	public Node(Object data) {
    		this.data = data;
    	}
    
    }
    
    public class LinkNode {
    	
    	private Node head;//头结点
    	private Node tail;//尾结点
    	private int size;
    
    	public LinkNode() {
    		this.head = null;
    		this.tail=null;
    		this.size = 0;
    	}
    
    	// 判断是否为空
    	public boolean isEmpty() {
    		return size == 0 ? true : false;
    	}
    
    	// 头插入法
    	public void addHNode(Node node) {
    		if (head == null) {
    			head = node;
    			tail=node;
    		} else {
    			node.next = head;
    			head = node;
    		}
    		size++;
    	}
    	
    	//尾结点插入
    	public void addTnode(Node node) {
    		if(head==null) {
    			head=node;
    			tail=node;
    		}else {
    			tail.next=node;
    			tail=node;
    		}
    		size++;
    	}
    
    	// 输出头结点，不删除
    	public Object sysHNode() {
    		if (head == null) {
    			return null;
    		}
    		Object obj = head.data;
    		return obj;
    	}
    
    	// 输出头结点,并删除
    	public Object deleteHnode() {
    		if (head == null) {
    			return null;
    		}
    		Object obj = head.data;
    		if (head.next == null) {
    			head = null;
    		} else {
    			head = head.next;
    		}
    		size--;
    		return obj;
    	}
    	
    	//输出尾结点，并删除
    	public Object deleteTnode() {
    		if(head==null) {
    			return null;
    		}
    		Object obj=tail.data;
    		if(head==tail) {
    			head=null;
    			tail=null;
    		}else {
    			Node temp=head;
    			Node pre=null;//前一个结点
    			while(temp!=tail) {
    				pre=temp;
    				temp=temp.next;
    			}
    			pre.next=null;
    			tail=pre;
    		}
    		size--;
    		return obj;
    	}
    	
    	//输出链表
    	private void sysNode() {
    		if(head==null) {
    			System.out.println("链表为空");
    			return;
    		}
    		Node temp=head;
    		while(temp!=null) {
    			System.out.print(temp.data+"-->");
    			temp=temp.next;
    		}
    		System.out.println();
    	}
    	
    	//获取链表大小
    	public int getSize() {
    		// TODO Auto-generated method stub
    		return size;
    	}
    	
    	public static void main(String[] args) {
    		
    		LinkNode linkNode=new LinkNode();
    		int i;
    		Node node;
    		for(i=0;i<5;i++) {
    			 node=new Node(i);
    			linkNode.addHNode(node);
    		}
    		for(i=5;i<10;i++) {
    			 node=new Node(i);
    			linkNode.addTnode(node);
    		}
    		
    		linkNode.sysNode();
    		System.out.println("链表大小--》"+linkNode.getSize());
    		System.out.println("输出头结点并删除--》"+linkNode.deleteHnode());
    		System.out.println("输出尾结点并删除--》"+linkNode.deleteTnode());
    		linkNode.sysNode();
    		System.out.println("链表大小--》"+linkNode.getSize());
    		
    	}
    
    }

效果：

4-->3-->2-->1-->0-->5-->6-->7-->8-->9-->
    链表大小--》10
    输出头结点并删除--》4
    输出尾结点并删除--》9
    3-->2-->1-->0-->5-->6-->7-->8-->
    链表大小--》8

### 我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。 ###