双向链表的基本用法

墨蓝 2022-05-17 03:18 175阅读 0赞

**双向链表：**双向链表的每个结点既能指向下一个结点，又能指向前一个结点，双向链表既能从头结点向尾结点遍历，又能从尾结点向头结点遍历，既有一个头结点，又有一个尾结点。

package parking;
    
    
    class Node{
    	Object data;
    	Node pre;
    	Node next;
    	
    	public Node(Object obj) {
    		this.data=obj;
    	}
    }
    
    public class LinkTwoList {
    	
    	private Node head;//头结点
    	private Node tail;//尾结点
    	private int size;
    	
    	
    	public LinkTwoList() {
    		head=null;
    		tail=null;
    		size=0;
    	}
    	
    	//判断链表是否为空
    	private boolean isEmpty() {
    		return size==0?true:false;
    	}
    	
    	//返回链表大小
    	private int getSize() {
    		return size;
    	}
    	
    	//头插入法
    	private void addHnode(Object obj) {
    		Node node=new Node(obj);
    		if(head==null) {
    			head=node;
    			tail=node;
    		}else {
    			node.next=head;
    			head.pre=node;
    			head=node;
    		}
    		size++;
    	}
    	
    	//尾插入法
    	private void addTnode(Object obj) {
    		Node node=new Node(obj);
    		if(head==null) {
    			head=node;
    			tail=node;
    		}else {
    			tail.next=node;
    			node.pre=tail;
    			tail=node;
    		}
    		size++;
    	}
    	
    	//返回头部结点
    	private Object getHnode() {
    		if(head==null) {
    			System.out.println("该链表为空");
    			return null;
    		}
    		Object obj=head.data;
    		if(head==tail) {
    			head=null;
    			tail=null;
    		}else {
    			head=head.next;
    			head.pre=null;
    		}
    		size--;
    		return obj;
    	}
    	
    	//删除链表表尾结点
    	private Object getTnode() {
    		if(head==null) {
    			System.out.println("该链表为空");
    			return null;
    		}
    		Object obj=head.data;
    		if(head==tail) {
    			head=null;
    			tail=null;
    		}else {
    			tail=tail.pre;
    			tail.next=null;
    		}
    		size--;
    		return obj;
    	}
    	
    	//输出链表
    	private void sysNode() {
    		if(head==null) {
    			System.out.println("链表为空");
    		}else {
    			Node temp=head;
    			while(temp!=null) {
    				System.out.print(temp.data+"-->");
    				temp=temp.next;
    			}
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
    		LinkTwoList link=new LinkTwoList();
    		int i;
    		for(i=0;i<5;i++) {
    			link.addHnode(i);
    		}
    		for(i=5;i<9;i++) {
    			link.addTnode(i);
    		}
    		link.sysNode();
    		System.out.println("链表大小："+link.getSize());
    		System.out.println("删除头结点："+link.getHnode());
    		System.out.println("删除头结点："+link.getTnode());
    		link.sysNode();
    		System.out.println("链表大小："+link.getSize());
    	}
    
    }

效果：

4-->3-->2-->1-->0-->5-->6-->7-->8-->
    链表大小：9
    删除头结点：4
    删除头结点：3
    3-->2-->1-->0-->5-->6-->7-->
    链表大小：7

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