特点：1.链表是以节点的方式来存储的，链式存储。
2.每个节点包含data域，next域指向下一个节点。
3.链表各节点不一定连续存储。
4.链表分带头节点的链表和没有头节点的链表，根据实际需求确定。
1.单链表1.1 带头结点的链表
头节点（head）：1.不存具体的数据2.作用就是表示单链表头
增删改查代码实现:
（插入分为两种：1.直接插入表尾2.按照标号插入）
class SinglelinkedList{
//创建头节点，不存放具体的数值，不能动
private Node head =new Node(0,"");
//添加节点到链表的最后:找到当前链表的最后节点并将最后节点的next指向新的节点
public void add(Node node){
//因为head不能动，故需要一个辅助变量来帮助遍历
Node temp =head;
//遍历找到最后
while (true){
if (temp.next==null){
break;
}
temp=temp.next;
}
//将最后节点的next指向新的节点
temp.next=node;
}
//显示链表
public void showlist(){
//判断链表是否为空
if (head.next==null){
System.out.println("链表为空");
return;
}
Node temp =head.next;
while (true){
//判断是否到链表最后
if (temp==null){
break;
}
//不为空则输出,已经重写了tostring
System.out.println(temp);
temp=temp.next;
}
}
public void addByOrder(Node pokenode){
Node temp=head;//原因同上，头节点不能动，用辅助节点帮助遍历找到位置
//单链表所以需要找到添加位置的前一个结点
boolean flag=false;//标识要插入的node的序号是否已存在
while (true){
if(temp.next==null){
break;//已经在链表的最后
}
if(temp.next.number>pokenode.number){
break;//位置找到就在temp的后面插入
}
else if(temp.next.number==pokenode.number){
flag=true;//编号已存在
break;
}
temp=temp.next;//后移遍历
}
if(flag){
System.out.println("已存在编号不能加入");
}
else {
pokenode.next=temp.next;
temp.next=pokenode;
}
}
//修改节点的信息，根据number编号来修改，即number不能改
public void update(Node newnode){
if (head.next==null){
System.out.println("链表为空");
return;
}
Node temp=head;
boolean flag=false;
while (true){
if(temp==null){
break;//到最后了
}
if (temp.number== newnode.number){
//找到
flag=true;
}
temp=temp.next;
}
if(flag){
temp.name=newnode.name;
}
else {
System.out.println("没有找到");
}
}
public void delete(int no ){
Node temp=head;
boolean flag = false;
while (true){
if (temp.next==null){
break;
}
if (temp.next.number==no){
flag=true;
break;
}
temp=temp.next;
}
if (flag){
temp.next=temp.next.next;
}
else {
System.out.println("没找到");
}
}
}
2.双向链表：
弥补一些单链表的缺点：1.单链表查找只能是一个方向，双向链表可以向前向后
2.单向链表各项功能均需要依靠辅助节点temp，而双向链表可以实现自我删除
双向链表的功能实现：
1.遍历方式与单链表相同，只是可以有多个方向。
2.添加时（表尾）除了需要将temp的next指向新元素，还需要将新元素的pre指向temp
3.删除：双向链表可以实现自我删除某个节点，找到该节点后直接写入
temp.pre.next=temp.next;
即完成了自删除，而与单链表相同的是，删除掉的节点成为无效引用，将被GC（垃圾回收机制）处理。
代码实现增删改查：
package dsanda;
public class doublelinkedListtest {
public static void main(String[] args) {
System.out.println("test for doublelinkedlist");
Node1 OBJ1=new Node1(1,"PIKA");
Node1 OBJ2=new Node1(2,"ZHONGZI");
Node1 OBJ3=new Node1(3,"JIENI");
Node1 OBJ4=new Node1(4,"ZENGZENG");
DoublelinkedList doublelinkedList =new DoublelinkedList();
doublelinkedList.add(OBJ1);
doublelinkedList.add(OBJ2);
doublelinkedList.add(OBJ3);
doublelinkedList.add(OBJ4);
doublelinkedList.showlist();
Node1 newnode =new Node1(4,"BENDAN");
doublelinkedList.update(newnode);
doublelinkedList.showlist();
}
}
class Node1{
public int number;
public String name;
public Node1 next;//指向下一个节点
public Node1 pre;//指向前一个节点 默认均为null
public Node1(int number,String name){
this.number=number;
this.name=name;
}
@Override
public String toString(){
return "Node no="+number+" "+"name="+name;
}
}
class DoublelinkedList{
//创建头节点，不存放具体的数值，不能动
private Node1 head =new Node1(0,"");
public Node1 getHead(){
return head;
}
public void add(Node1 node){
//因为head不能动，故需要一个辅助变量来帮助遍历
Node1 temp =head;
//遍历找到最后
while (true){
if (temp.next==null){
break;
}
temp=temp.next;
}
//将最后节点的next指向新的节点并让新节点的pre指向temp
temp.next=node;
node.pre=temp;
}
public void showlist(){
//判断链表是否为空
if (head.next==null){
System.out.println("链表为空");
return;
}
Node1 temp =head.next;
while (true){
//判断是否到链表最后
if (temp==null){
break;
}
//不为空则输出,已经重写了tostring
System.out.println(temp);
temp=temp.next;
}
}
public void update(Node1 newnode){
if (head.next==null){
System.out.println("链表为空");
return;
}
Node1 temp=head;
boolean flag=false;
while (true){
if(temp==null){
break;//到最后了
}
if (temp.number== newnode.number){
//找到
flag=true;
break;
}
temp=temp.next;
}
if(flag){
temp.name=newnode.name;
}
else {
System.out.println("没有找到");
}
}
//从双向链表中删除时可以做到自删除
public void delete(int no ){
//判断是否为空
if(head.next==null){
System.out.println("链表为空");
return;
}
Node1 temp=head.next;
boolean flag = false;
while (true){
if (temp==null){//已经到了最后节点的next
break;
}
if (temp.number==no){
flag=true;
break;
}
temp=temp.next;
}
if (flag){
temp.pre.next=temp.next;
//如果需要删除的节点为左后一个，则不应执行下一句
if(temp.next!=null){
temp.next.pre=temp.pre;}
}
else {
System.out.println("没找到");
}
}
}
3.环形链表
即最后一个节点的next指向第一个节点
引入 约瑟夫问题应用单向环形链表：
public class roundlinkedList {
public static void main(String[] args) {
roundSinglelinkedList roundSinglelinkedList=new roundSinglelinkedList();
roundSinglelinkedList.addBoy(5);
roundSinglelinkedList.showboy();
roundSinglelinkedList.countBoy(1,2,5);
}
}
class roundSinglelinkedList{
private boy first=new boy(-1);
//添加节点构建黄兴链表
public void addBoy(int nums){
if (nums<1){
System.out.println("nums值不正确");
return;
}
boy curboy=null;
//使用for创建环形链表
for (int i=1;i<=nums;i++){
boy boy1=new boy(i);
if (i==1){
first=boy1;
first.setNext(first);//成环
curboy=first;//让cur指向第一个小孩
}else {
curboy.setNext(boy1);
boy1.setNext(first);
curboy=boy1;
}
}
}
public void showboy(){
if (first==null){
System.out.println("空");
return;
}
//first不能动，利用辅助指针完成遍历
boy curboy=first;
while (true){
System.out.println("小孩的编号为"+curboy.getNo());
if (curboy.getNext()==first){
break;//说明已经遍历完成
}
curboy=curboy.getNext();//后移
}
}
//根据用户的输入计算出 出圈的顺序
public void countBoy(int startNo,int countNum,int nums){
if (first==null||startNo<1||startNo>nums){
System.out.println("参数输入有误，请重新输入");
return;
}
//创建辅助指针
boy helper = first;
while (true){
if (helper.getNext()==first){
break;//说明helper指向最后成员的节点
}
helper=helper.getNext();
}
//小孩报数前，先让first和helper移动k-1次
for (int j=0;j
