JAVA链表实现与链表的逆序

1.链表

        链表有单链表还有双向链表,在java中每个节点都是一个类,这里声明了内部类,为了方便插入和删除,有时会在,链表的表头加上哨兵(形成有哨兵的循环或双向循环链表),这样的插入删除就不用考虑当插入删除的元素在边界的情况,方便,至于哨兵你可能觉得没什么用,其实他可以存储链表的许多信息,比如你每次查找一个元素,在无哨兵时,使用P!=null,使用哨兵,可以存储要查找的元素,退出时,就要判断是不是哨兵。

2.链表的实现与逆序

  若想代码写得快,必须清楚每次交换插入,产生的状态和性质。在写代码时,一个节点指错了下一个节点,导致调了好长时间,一定要想清楚每次变换的状态结果。下面使用了两种方法实现,链表的逆序,这两个思路都是插入排序的思想,只是迭代反向不同。

思路一:从第n-1个元素开始向前迭代,一次插入到链表结尾,在为双向链表并且含有尾节点时,时间复杂度为:n,在当链表为 n的平方。因为还要查找节点。

思路二:从第2-n个节点一次向后迭代,插入到head节点位置,一次向后就能每次使用next保存下一次要插入的元素,一路走来,不用查找节点。

同样的思路不同的方向,向前面插向后面插,双向思考

代码如下:

class List<T> {
	private static class Node<T>{
		private T key;
		Node<T> next;
		public Node(T key,Node<T> next)
		{
			this.key=key;
			this.next=next;
		}
	}
	private int size;
	private Node<T> head;
	public List(){
		size=0;
		head=null;
	}
	public int size()
	{
		return size;
	}
	public boolean isEmpty()
	{
		if(size==0)
			return true;
		else
			return false;
	}
	public void insert(T key)
	{
		head=new Node<T>(key,head);
		size++;
	}
	public T front()
	{
		return  head.key;
	}
	public T get(int index)
	{
		if(index>=size||index<0)
			return null;
		int i=0;
		Node<T>p=head;
		while(i++<index)
			p=p.next;
		return p.key;
	}
	public T delete(){
		T x=head.key;
		head = head.next;
		size--;
		return x;
	}
	public void delete(T key){
		Node<T>node=searchNode(key);
		if(node==null)
			return ;
		
		if(size==1)
			head=null;
		else
		{
		    Node<T>pre=head;
		    while(pre.next!=null&&pre.next!=node)
			pre=pre.next;
		    pre.next=node.next;
		}
		size--;
	}
	public Node<T> searchNode(T key)
	{
		Node<T> p= head;
		int i=0;
		while(p!=null&&p.key!=key)
			p=p.next;
		return p;
	}
	public int searchIndex(T x)
	{
		Node<T> p= head;
		int i=0;
		
		while(p!=null&&p.key!=x)
		{
			i++;
			p=p.next;
			
		}
		if(p!=null)
		return i;
		return -1;
	}
	public Node<T> getNode(int index)
	{
		if(index<0&&index>=size)
			return null;
		int i=0;
		Node<T>p=head;
		while(i++<index)
			p=p.next;
		return p;
	}
	/**
	 * 求链表的逆序  注意一定要链接节点时 连接对
	 * 思路一:这个比较麻烦:是把前面的元素从后向前一次放在链表结尾
	 * 还要查找元素节点,查找过程为n所以时间复杂度已经为 :n的平方 了
	 */
	public void reverse(){
		if(size<=1)
			return ;
		int i=size-2;
		Node<T>tail=getNode(size-1);
		while(i>=0)
		{
             Node<T>e=getNode(i);
             if(e!=head)
             {
            	 Node<T>pre=getNode(i-1);
                 tail.next=e;
                 pre.next=e.next;
                 tail=e;
                 tail.next=null;
             }
             else 
             {
            	 tail.next=head;
            	 tail=head;
            	 head=head.next;
            	 tail.next=null;
             }
             i--;
		}
	}
	
	/**
	 * 思路二: 从后面像最前面插入,插入排序的思想
	 */
	public void reverse2()
	{
		if(size<=1)
			return ;
		int i=1;
		Node<T>pre,insertNode,next;
		pre=head;
		next=head.next;//每个要插入元素的头结点都是最初的头结点
		while(i++<size)
		{
			insertNode=next;
			if(next.next!=null)
			next=next.next;
            pre.next=insertNode.next;  			
			insertNode.next=head;
			head=insertNode;
		}
		
	}
	/*使用java的值传递,是复制了一份引用的副本,不是原来的引用
	 * ,虽然指向相同,这样是不能把链表转换为逆序的
	 * public void swap(Node<T>head)
	
	{
		if(head.next!=null)
		{
			Node<T>p=head;
			swap(p.next);
			T key=head.key;
			while(p!=null)
				p=p.next;
			p.next=head;
			head=p.next;
		}
		
	}*/
}
public class SingleList {
    public static  void main(String args[])
    {
    	List<Integer> list=new List<Integer>();
    	list.insert(1);
    	list.insert(2);
    	list.insert(3);
    	list.insert(4);
    	list.insert(5);
    	list.reverse2();
    	System.out.println(list.get(0)+" "+list.get(1)+" "+list.get(2)+" "+list.get(3)+" "+list.get(4)+" ");
    }
}



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。