Java实现双向链表

女爷i 2023-07-09 03:29 13阅读 0赞

[*点击进入尚硅谷数据结构和算法Java代码导航*][Java]

public class TwoWayList<T> {
        
    
    	private class Node{
        
    		T data;
    		Node next = null;
    		Node prev = null;
    		public Node(T t) {
        
    			this.data = t;
    		}
    	}
    	
    	private Node head;
    	private int len;
    	
    	public TwoWayList() {
        
    		this.head = new Node(null);
    		this.len = 0;
    	}
    	
    	//获取第index个节点
    	public Node getNode(int index) {
        
    		Node temp = head;
    		for(int i=0; i<index; i++) {
        
    			temp = temp.next;
    		}
    		return temp;
    	}
    	
    	//向尾部添加节点
    	public void addTail(T t) {
        
    		Node temp = new Node(t);
    		Node last = getNode(len);
    		last.next = temp;
    		temp.prev = last;
    		len++;
    	}
    	//转换为循环链表
    	public void toCircular() {
        
    		Node last = getNode(len);
    		last.next = head;
    		head.prev = last;
    	}
    	
    	//向index位置后面插入节点
    	public boolean insert(T t, int index) {
        
    		if(index<0 || index>len) {
        
    			System.out.println("Insert failed, index error!");
    			return false;
    		}
    		if(index == len) {
        
    			addTail(t);
    			return true;
    		}
    		Node prev = getNode(index);
    		Node next = getNode(index+1);
    		Node temp = new Node(t);
    		temp.next = next;
    		temp.prev = prev;
    		prev.next = temp;
    		next.prev = temp;
    		len++;
    		return true;
    	}
    	
    	//删除Index位置的节点
    	public T delete(int index) {
        
    		if(index<0 || index>len) {
        
    			throw new IndexOutOfBoundsException("Delete failed, Index error!");
    		}
    		if(index == len) {
        
    			Node temp = getNode(index);
    			T t = temp.data;
    			Node prev = getNode(index-1);
    			prev.next = null;
    			len--;
    			return t;
    		}
    		Node prev = getNode(index-1);
    		Node next = getNode(index+1);
    		Node temp = getNode(index);
    		T t = temp.data;
    		prev.next = next;
    		next.prev = prev;
    		len--;
    		return t;
    	}
    	
    	
    	//正向输出链表
    	public void forwardp() {
        
    		Node temp = head;
    		for(int i=0; i<=len; i++) {
        
    			System.out.print(temp.data + "->");
    			temp = temp.next;
    		}
    		System.out.print(" length:" + len + "\n");
    	}
    	//反向输出链表
    	public void backp() {
        
    		Node temp = getNode(len);
    		for(int i=0; i<=len; i++) {
        
    			System.out.print(temp.data + "<-");
    			temp = temp.prev;
    		}
    		System.out.print(" length:" + len + "\n");
    	}
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    
    		TwoWayList<Integer> twl = new TwoWayList<Integer>();
    		twl.addTail(1);
    		twl.addTail(2);
    		twl.insert(3, 2);
    		twl.insert(4, 3);
    		twl.addTail(5);
    		twl.delete(5);
    		twl.forwardp();
    		twl.backp();
    	}
    }

[Java]: https://blog.csdn.net/weixin_44963741/article/details/105228982