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