数据结构（链表）-开发者社区

链表

链表是节点这种存储结构加上对节点的一套操作方法

节点

节点的结构包括存储的数据类型以及指向下一个节点的指针。

publicclassMyLinkedList{//节点属性：节点 指向下一个的指针publicclassNode{Objectvalue;Nodenext;publicNode(Objectvalue){this.value=value;this.next=null;}}

操作方法

//链表属性：头节点、尾节点和链表长度Nodehead;intsize;Nodelast;//操作方法：publicMyLinkedList(){this.head=null;this.size=0;this.last=null;}

这里的head和last并不是指头节点和尾节点，而是指向头节点和尾节点的指针，可以说它们像一个标签，贴在头节点和尾节点上面，负责帮计算机一下子定位到头尾的位置。

add方法

publicvoidadd(Objectvalue){NodenewNode=newNode(value);//如果链表为空if(head==null){head=newNode;//此时链表中只有一个节点，头尾都指向这个节点}else{//时间复杂度为n,当数据量大时，耗费时间长// Node temp=head;//从头节点往后找// while(temp.next!=null){// temp=temp.next;// }// temp.next=newNode;//时间复杂度为1last.next=newNode;//将原本的最后一个节点变成倒数第二个节点}last=newNode;//让尾部标签指向这个节点size++;}

remove方法

找到被删除元素的前驱节点，然后将前驱节点与被删除元素的后继节点连接

publicNodefindFirstNode(Objectkey){Nodetemp=head;while(temp.next!=null){if(temp.next.value==key){returntemp;//返回要删除元素的前驱节点}temp=temp.next;//继续移动遍历元素}returnnull;}//删除找到的第一个节点publicvoidremove(Objectkey){if(head==null){return;}//如果头节点就是if(head.value==key){head=head.next;size--;return;}Nodecur=findFirstNode(key);if(cur!=null){Nodedel=cur.next;cur.next=del.next;size--;}}

insert方法

链表必须通过遍历才能到达索引位置

//在任意位置插入节点publicvoidinsert(intindex,Objectvalue){if(head==null||isIndexOutBound(index)){return;}Nodecur=head;for(inti=0;i<index-1;i++){cur=cur.next;}//找到要插入位置的前驱节点cur//新节点先与后一节点连接，再把cur的后驱连接到新节点上NodenewNode=newNode(value);newNode.next=cur.next;cur.next=newNode;size++;}

contains方法

//查找元素：找到返回truepublicbooleancontains(Objectkey){if(head==null){returnfalse;}Nodetemp=head;while(temp!=null){if(temp.value==key){returntrue;}temp=temp.next;}returnfalse;}

如果在while循环里面将条件全部设为“temp.next”则会漏掉头节点——当链表中只有一个节点while的进入条件为假，直接退出程序返回false;当链表中有多个节点，if直接判断第二个节点是否是要找的元素。
如果只将进入while循环的条件设为"temp.next"则又会漏掉尾节点——当循环遍历到尾节点，进入条件判断为假，返回false.而在倒数第二个节点处，if判断的是当前元素，不是尾节点元素。

测试

staticvoidmain(){MyLinkedListl1=newMyLinkedList();l1.add(1);l1.add(2);l1.insert(1,9);System.out.println(l1.contains(9));System.out.println(l1.contains(1));System.out.println(l1.contains(2));l1.remove(1);System.out.println(l1.contains(1));}