创建一个单链表类——SinglyLinkedList,继承线性表LList

古城微笑少年丶 2022-08-14 03:54 110阅读 0赞

/*声明一个带头指针的单链表
     * 
     * */
    
    package DataStructureTestSinglyLinkedList;
    import DataStructureTest.LList;
    
    public class SinglyLinkedList<T> implements LList<T> {
    	
    	public Node<T> head;
    	
    	//无参构造函数
    	public SinglyLinkedList()
    	{
    		this.head=new Node<T>();
    	}
    	
    	//带参构造函数，参数是一个T类型数组,采用尾插法插入
    	public SinglyLinkedList(T[] element)
    	{
    		this();
    		Node<T> rear=this.head;
    		for(int i=0;i<element.length;i++)
    		{
    			rear.next=new Node<T>(element[0],null);
    			rear=rear.next;
    		}
    		
    	}
    
    	@Override
    	public boolean isEmpty() {
    		// TODO 自动生成的方法存根
    		return this.head.next==null;
    	}
    
    	@Override
    	public int length() {
    		// TODO 自动生成的方法存根
    		int len=0;
    		Node<T> p= this.head.next;
    		while(p!=null)
    		{
    			len++;
    			p=p.next;
    			
    		}
    			
    		
    		return len;
    	}
    
    	@Override
    	public T get(int i) {
    		// TODO 自动生成的方法存根
    		if(i>=0)
    		{
    			Node<T> p= this.head.next;
    			for(int j=0;j<i;j++)
    				p=p.next;
    			if(p!=null)
    				return p.data;
    		}
    		
    	
    		return null;
    	}
    	
    	public void set(int i , T x)
    	{
    		if(x==null)
    			return;
    		if(i>=0)
    		{
    			Node<T> p= this.head.next;
    			for(int j=0;j<i;j++)
    				p=p.next;
    			if(p!=null)
    				p.data=x; 
    		}
    		else throw new IndexOutOfBoundsException(i+"索引有误");
    	}
    
    
    
    	@Override
    	public void insert(int i, T x) {
    		// TODO 自动生成的方法存根
    		if(x==null)
    			return ;
    		Node<T> p=this.head;
    		for(int j=0;p.next!=null&&j<i;j++)
    			p=p.next;
    		p.next=new Node<T>(x,p.next);
    	}
    
    	@Override
    	public void append(T x) {
    		// TODO 自动生成的方法存根
    		insert(Integer.MAX_VALUE,x);
    	}
    
    	@Override
    	public T remove(int i) {
    		// TODO 自动生成的方法存根
    		if(i>=0)
    		{
    			Node<T> p = this.head;
    			for(int j=0;p.next!=null && j<i;j++)
    				p=p.next;
    			if(p.next!=null)
    			{
    				T old = p.next.data;
    				p.next=p.next.next;
    				return old;
    			}
    			
    		}
    		return null;
    		
    	}
    
    	@Override
    	public void removeAll() {
    		// TODO 自动生成的方法存根
    		this.head.next=null;
    	}
    
    	@Override
    	public T search(T key) {
    		// TODO 自动生成的方法存根
    		
    		return null;
    	}
    
    
    	public String toString()
    	{
    		String str="(";
    		Node<T> p = this.head.next;
    		while(p!=null)
    		{
    			
    				str+=p.data.toString();
    				if(p.next!=null)
    					str+=",";
    				p=p.next;
    			
    		}
    		
    		
    		return str+")";
    	}
    	
    
    }