数据结构(Java)-第2章线性表-链表

//在不确定数据域数值的情况下，采用泛型定义publicclassNode<E>{Edata;//数据域Node<E>next;//指针域}datanext单个节点的表示方法//在不确定数据域数值的情况下，采用泛型定义publicclassLinkList<E>{ Node<E>head;Node<E>p;}datanext单个节点的表示方法datanextdatanextheadnull建立链表datanextheadNULLnewnode//说明head头指针newnode新节点指针newnode.data数据域表示方式newnode.next指针域表示方式NULLnewnode无后继节点headNULLPNULL初始状态,无节点

head=NULL;P=NULL;publicLinkList(){head=null;p=null;}初始化datanextheadNULLpnewode建立链表publicvoidaddhead(Node<E>e){Node<E>newhead=newNode<E>();newhead.data=e.data;newhead.next=e.next;head=newhead;p=head;p.next=null;}遍历输出publicvoidprintlist(){ p=head; if(head==null) {System.out.println("这是一个空链表"); }while(p!=null)

{System.out.println(p.data); p=p.next; }}在链表后面插入节点datanextheadNULLnewnodedatanextp注意：添加节点后，链表的长度+1publicvoidaddlist(Node<E>e){Node<E>newnode=newNode<E>();newnode.data=e.data;newnode.next=e.next;p.next=newnode;p=p.next;p.next=null;}publicstaticvoidmain(String[]args){ScannerAA=newScanner(System.in);LinkList<Integer>obj1=newLinkList<Integer>();Node<Integer>tt=newNode<Integer>();System.out.print("请输入第1数:");tt.data=AA.nextInt();obj1.addhead(tt);Node<Integer>tb=newNode<Integer>();intk;inti=2;do{System.out.print("请输入第"+i+"数:");k=AA.nextInt();if(k==0)break;tb.data=k;obj1.addlist(tb);i++;}while(true);此段代码:表示连续建立多个节点，知道输入的数字为0，就不再建立新的节点obj1.printlist();System.out.print("请输入第插入节点的值");tb.data=AA.nextInt();obj1.addnode(tb,2);obj1.printlist();System.out.print("请输入首节点插入的值");tb.data=AA.nextInt();obj1.addH(tb);obj1.printlist();}单链表的插入（1）只定节点后插入新的节点图示

s.next=p.next;p.next=s;(2)前插结点

（2）只定节点前插入新的节点图示

s.next=p;q.next=s;单链表的删除

q.next=p.next;p.next=null;单链表的按值查找操作 }

单链表操作的效率分析

（1）单链表是一种顺序存取结构，不是随机存取结构。要访问任意一个结点ai（1≤i≤n），必须从头指针head开始，沿着“链”的方向逐个查找，执行i-1次p=p.getNext()操作，平均进行n/2次。（2）单链表的插入和删除操作，必须知道其直接前驱结点。（3）与顺序表相比，单链表中结点的存储空间是动态申请和释放的，不需要预先分配。同时，对单链表执行插入和删除操作时，只需要改变相关结点的“链”，不需要移动结点。因此，单链表在一定程度上可以提高运行效率和存储空间的利用率。循环链表

head是单链表的头指针，设rear是单链表的尾指针。将单链表中最后一个结点的指针域指回链表的头结点，即rear.next=head，则整个单链表头尾相连形成了一个环，就构成了循环单链表。

双向链表

在单链表中，从任意一个结点出发都能通