动手写一个双向链表

女爷i 2023-06-13 06:06 1阅读 0赞

单向链表就不写了，进来直接写双向链表。  
首先需要了解双向链表的接口。将链的节点抽象为一个对象，对象存在两个指针，一个指向前面一个节点，一个指向后面一个节点。  
实现双向链表的功能就是对链的指针操作。

package com.linked;
    
    /** * 实现双向链表 * @author T */
    public class LinkedTable<T> { 
    	
    	private Node<T> head;
    	private Node<T> tail;
    	private int size;
    	
    	
    	//head不存入数据
    	public void addFirst(T data){ 
    		Node node = null;
    		//如果head为空，表明链表为空。
    		if(head == null){ 
    			node = new Node(data,null,null);
    			tail = node;
    		} else { 
    			node = new Node(data,null,head);
    			head.previous = node;
    		}
    		head = node;
    		size++;
    	}
    	
    	//head不存入数据
    	public void addLast(T data){ 
    		Node node = null;
    		if(tail == null){ 
    			node = new Node(data,null,null);
    			head = node;
    		} else { 
    			node = new Node(data,tail,null);
    			tail.next = node;
    		}
    		tail = node;
    		size++;
    	}
    	
    	public T getFirst(){ 
    		return head.data;
    	}
    	
    	public T getLast(){ 
    		return tail.data;
    	}
    	
    	/** * 通过索引获取索引所对应节点的值 * @param index * @return */
    	public T get(int index){ 
    		if(index < 0 || index > size){ 
    			throw new IndexOutOfBoundsException();
    		}
    		if(index == 0){ 
    			return getFirst();
    		}
    		if(index == size-1){ 
    			return getLast();
    		}
    		Node<T> node = getNode(index);
    		return node.data;
    	}
    	
    	
    	public int size(){ 
    		return size;
    	}
    	
    	/** * 获取索引节点 * @param index * @return */
    	private Node<T> getNode(int index){ 
    		if(index < 0 || index > size){ 
    			throw new IndexOutOfBoundsException();
    		}
    		Node<T> node = head;
    		for (int i = 0; i < index; i++) { 
    			node = node.next;
    		}
    		return node;
    	}
    	
    	/** * 实现索引加入，索引节点的前方加入 * @param data * @param index */
    	public void add(T data,int index){ 
    		//获取索引对应的节点
    		Node node = getNode(index);
    		
    		//创建newNode与前后的关系，previous指向node的前面节点，next指向node
    		Node newNode = new Node(data,node.previous,node);
    		
    		//建立前一个节点与newNode的关系
    		node.previous.next = newNode;
    		
    		//建立后一个节点node与newNode的关系
    		node.previous = newNode;
    		
    		size++;
    	}
    	
    	
    	public void delete(int index){ 
    		if(index == 0){ 
    			head.next.previous = head.previous;
    			head = head.next;
    		} else { 
    			Node<T> node = getNode(index);
    			node.previous.next = node.next;
    			node.next.previous = node.previous;
    		}
    		size--;
    	}
    	
    	
    	
    	/** * 建立链表最小单元-链 * @author T * @param <T> */
    	class Node<T>{ 
    		private T data;
    		private Node<T> previous;
    		private Node<T> next;
    		
    		
    		public T getData() { 
    			return data;
    		}
    		public void setData(T data) { 
    			this.data = data;
    		}
    		
    		public Node(T data){ 
    			this.data = data;
    		}
    		public Node<T> getPrevious() { 
    			return previous;
    		}
    		public void setPrevious(Node<T> previous) { 
    			this.previous = previous;
    		}
    		public Node<T> getNext() { 
    			return next;
    		}
    		public void setNext(Node<T> next) { 
    			this.next = next;
    		}
    		
    		/** * @param data 真实数据 * @param previous 前置 * @param next 后置 */
    		public Node(T data, Node<T> previous, Node<T> next) { 
    			this.data = data;
    			this.previous = previous;
    			this.next = next;
    		}
    		
    		
    		
    	}
    
    }

测试一下：

package com.linked;
    
    public class LinkedTableTest { 
    	
    	public static void main(String[] args) { 
    		LinkedTable<String> lt = new LinkedTable<String>();
    		lt.addFirst("10");
    		lt.addFirst("11");
    		lt.addFirst("12");
    		lt.addFirst("13");
    		lt.addFirst("14");
    		lt.addFirst("15");
    		
    		lt.add("10.5", 1);
    		
    		System.out.println("==ready==");
    		
    		for (int i = 0; i < lt.size(); i++) { 
    			System.out.println(lt.get(i));
    			System.out.println("---------------");
    		}
    		System.out.println("==delete==");
    		lt.delete(1);
    		for (int i = 0; i < lt.size(); i++) { 
    			System.out.println(lt.get(i));
    			System.out.println("---------------");
    		}
    	}
    
    }