---

什么是链表

数组的数据结构为连续的存储空间,由于空间连续因此进行访问时的效率很高,但是同时删除和插入数据的效率很低,因此提出了链表这一概念.与数组不同,链表的存储并不连续,下图为链表的存储空间示意图.可以发现a1并不在最高地址(110),而next却指向了下一个数据a2.这也就是链表的特点,数据域data地址不连续,依靠指针域next指向下一个元素.

1)链表是以节点的方式来存储,是链式存储
2)每个节点包含 data 域,next 域:指向下一个节点.
3)链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

一、单链表基本结构

C/C++版本链表
按照上面的规定实现data数据域,next指针域,与C/C++语言不同,Java没有指针符号*,而是靠对象引用来传递地址,因为一个对象本身就能调用其所在类的方法并且访问成员数据,也就实现了类似结构体与指针的效果.

class LinkedList_ implements Cloneable{public int data;public String name;public LinkedList_ next;public LinkedList_(int data,String name) {this.data = data;this.name = name;}@Overridepublic LinkedList_ clone(){LinkedList_ temp=null;try {//如果该类没有实现CLoneable接口那么就会抛出异常temp = (LinkedList_)super.clone();//先拷贝父类中的基本消息\temp.next=null;//之后如果子类中有一些可变对象(如Date),那么就需要进行深拷贝//temp.date = (Date)new Date().clone();如下就} catch (CloneNotSupportedException e) {e.printStackTrace();}return temp;}@Overridepublic String toString() {return "LinkedList_{" +"data=" + data +", name='" + name + '\'' +'}';}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;LinkedList_ list = (LinkedList_) o;return data == list.data && Objects.equals(name, list.name) ;}@Overridepublic int hashCode() {return Objects.hash(data, name, next);}
}

---

二、功能实现

• 1:添加元素 2:删除元素 3:修改元素 4:查询元素
• 5:融合两个单链表 6:反转单链表
• 7:获取倒数第x个元素 8:倒序查询

添加元素

public void add(LinkedList_ list)//按照元素大小排序{boolean flag=false;//判断元素是否存在标志位LinkedList_ temp=head;//head是存放当前链表的头指针while(temp.next!=null){//由于有头指针的存在因此需要判断的temp.next而不是tempif(temp.next.data>list.data){//判断已有元素与插入元素的大小break;  //如果插入元素更小那么直接退出循环准备插入}else if(temp.next.data==list.data){//判断元素是否已经存在flag=true;break;}temp=temp.next;}if(flag){System.out.println("当前元素已经存在");}else{list.next=temp.next;//元素插入temp.next=list;}}

---

删除元素

public void delete(LinkedList_ dellist)//删除某个元素{if(head.next==null){ //先判断链表是否为空System.out.println("链表为空");return;}LinkedList_ temp=head;while(temp.next!=null){ //先判断下一个元素是否存在 if(temp.next.equals(dellist)){ //存在后再判断是否是要删除的元素temp.next=temp.next.next;//如果是那么就直接让指针指向要删除元素的下一个元素break;  //之后只需要等待Java的垃圾回收机制来主动回收即可}temp=temp.next; //不是要删除的元素则指针向下}}

---

修改元素

    public void update(LinkedList_ newlist)//根据newlist的data来修改{if(head.next==null){System.out.println("链表为空");return;}LinkedList_ temp=head;while(temp.next!=null){ //如果遇到了要删除的元素的data域if(newlist.data==temp.next.data){ //那么就修改其name域temp.next.name= newlist.name;}temp=temp.next; //不是就指向下一个元素}}

---

遍历

 public void traverse()//遍历单链表{if(head.next==null){System.out.println("链表为空");return;}LinkedList_ temp=head;while(temp.next!=null){System.out.println(temp.next);temp=temp.next;}}

---

融合链表

    public void addTwoOrderedList(SingleLinkedList otherList)//连接两个单链表{
//        boolean flag=false;LinkedList_ list=otherList.head.next;while(list!=null) {//其实就是先遍历要加入的链表 LinkedList_ temp=this.head; //然后把这个链表按照add方法中添加到原先的单链表即可boolean flag=false;while (temp.next != null) {if (temp.next.data > list.data) {break;} else if (temp.next.data == list.data) {flag = true;break;}temp = temp.next;}if (flag) {System.out.println("当前元素已经存在");} else {//到这里说明list比temp.next小//使用clone方法是为了不让原有的list的指针域也被连接上去LinkedList_ newlist = (LinkedList_) list.clone();
//                LinkedList_ newlist=new LinkedList_(list.data,list.name);LinkedList_ next = temp.next;temp.next=newlist;newlist.next=next;}list=list.next;}}

---

反转元素

  public SingleLinkedList reverse()//反转{SingleLinkedList newlist=new SingleLinkedList();LinkedList_ cur = this.head.next; //第一个有效数据LinkedList_ temphead = newlist.head;LinkedList_ tempnext = null;//方法一 效率低的反转 但是原有单链表不会被破坏//方法一思路:两个for循环 外层for循环用于指明已经遍历了几个元素//内层for循环用于将元素指向待插入的最后一个元素//例如第一次外层for i=0 那么内层就需要进行最多次数的temp=temp.next;  ////那么就可以得到最后一个元素 第二次就可以得到倒数第二个元素 以此类推
//        int length = this.getLength();
//        for(int i=0;i<length;i++) { //length=6
//        LinkedList_ temp= this.head; //0 0 1 2 3 4 5
//            for(int j=length;j>i;j--) {
//                temp=temp.next;  //
//            }
//            temphead.next=temp.clone();
//            temphead=temphead.next;
//        }
//        temphead.next=null;//方法二 效率更高的反转 但是调用该函数的单链表将会被破坏while(cur!=null){tempnext=cur.next;cur.next=temphead.next;temphead.next=cur;cur=tempnext;}//方法三 按照方法一遍历 将遍历的元素存储到数组中去//然后倒序将数组的元素插入到新的链表即可 return newlist;}

---

获取倒序第x个元素

public LinkedList_ getLastIndexNode(int lastIndex)//获取倒数第x个的数据元素{if(head.next==null||(this.getLength()<lastIndex)||lastIndex<0){System.out.println("链表为空/查询数据索引不合理");return null;}LinkedList_ temp=head.next; //第一个有效数据 去掉头指针int time=this.getLength()-lastIndex;//获取到这个元素需要遍历的次数for(int i=0;i<time;i++){temp=temp.next;}return temp;}

---

倒序遍历

public void reverseTraverse()//倒序遍历{//方法一 遍历链表并将数据加入到链表中去, 然后倒序输出链表
//        int i=this.getLength();
//        LinkedList_ temp=head;
//        LinkedList_[]listArr=new LinkedList_[i];
//        while(temp.next!=null){
//            listArr[--i]=temp.next;
//            temp=temp.next;
//        }
//        System.out.println(Arrays.toString(listArr));//方法二 直接遍历
//        for(int j=0;j<this.getLength();j++){
//            LinkedList_ temp=head;
//           for(int k=this.getLength();k>j;k--){
//               temp=temp.next;
//           }
//            System.out.println(temp);
//        }//方法三 使用栈Stack<LinkedList_> stack = new Stack<>();LinkedList_ temp=this.head.next;while(temp!=null){stack.add(temp);temp=temp.next;}while(stack.size()>0){System.out.println(stack.pop());}}

---

完整代码

package algorithm.DataStruct.LinkList;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Objects;
import java.util.Stack;/*** @author: Serendipity* Date: 2022/1/25 21:11* Description:* 1:添加元素  2:删除元素 3:修改元素 4:查询元素* 5:融合两个单链表  6:反转单链表 7:获取倒数第x个元素 8:倒序查询*/
public class SingleLinkedList{public static void main(String[] args) {functionChoose();}private final LinkedList_ head=new LinkedList_(0,"");public LinkedList_ getHead(){return head.next;}public static void functionChoose(){SingleLinkedList list1 = new SingleLinkedList();SingleLinkedList list2 = new SingleLinkedList();try(BufferedReader br=new BufferedReader(new InputStreamReader(System.in))){while (true){System.out.println("功能选择");System.out.println("1:顺序插入");System.out.println("2:删除元素");System.out.println("3:修改元素");System.out.println("4:显示元素");System.out.println("5:反转链表");System.out.println("6:获取倒数x的元素");System.out.println("7:倒序遍历");System.out.println("8:融合两个链表");System.out.println("9:退出");int choose = Integer.parseInt(br.readLine());switch (choose){case 1->{System.out.println("选择要插入的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{System.out.println("输入要插入的数据data与name");list1.add(new LinkedList_(Integer.parseInt(br.readLine()),br.readLine()));break;}default -> {System.out.println("输入要插入的数据data与name");list2.add(new LinkedList_(Integer.parseInt(br.readLine()),br.readLine()));}}break;}case 2->{System.out.println("选择要删除数据的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{System.out.println("输入要删除的数据data与name");list1.delete(new LinkedList_(Integer.parseInt(br.readLine()),br.readLine()));break;}default -> {System.out.println("输入要删除的数据data与name");list2.delete(new LinkedList_(Integer.parseInt(br.readLine()),br.readLine()));}}break;}case 3->{System.out.println("选择要修改数据的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{System.out.println("输入要修改的数据data,并输入新的name");list1.update(new LinkedList_(Integer.parseInt(br.readLine()),br.readLine()));break;}default -> {System.out.println("输入要修改的数据data,并输入新的name");list2.update(new LinkedList_(Integer.parseInt(br.readLine()),br.readLine()));}}break;}case 4->{System.out.println("选择要查询数据的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{list1.traverse();break;}default -> {list2.traverse();}}break;}case 5->{System.out.println("选择要反转数据的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{list1.reverse();break;}default -> {list2.reverse();}}break;}case 6->{System.out.println("选择要查询的倒数数据的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{System.out.println("输入倒数的数据");choose = Integer.parseInt(br.readLine());System.out.println(list1.getLastIndexNode(choose));break;}default -> {System.out.println("输入倒数的数据");choose = Integer.parseInt(br.readLine());System.out.println(list2.getLastIndexNode(choose));}}break;}case 7->{System.out.println("选择要倒序遍历数据的链表号1/2");choose = Integer.parseInt(br.readLine());switch (choose){case 1->{list1.reverseTraverse();break;}default -> {list2.reverseTraverse();}}break;}case 8->{list1.addTwoOrderedList(list2);break;}case 9->System.exit(0);}}}catch (Exception e){e.printStackTrace();}}public void add(LinkedList_ list)//按照元素大小排序{boolean flag=false;//判断元素是否存在标志位LinkedList_ temp=head;//head是存放当前链表的头指针while(temp.next!=null){//由于有头指针的存在因此需要判断的temp.next而不是tempif(temp.next.data>list.data){//判断已有元素与插入元素的大小break;  //如果插入元素更小那么直接退出循环准备插入}else if(temp.next.data==list.data){//判断元素是否已经存在flag=true;break;}temp=temp.next;}if(flag){System.out.println("当前元素已经存在");}else{list.next=temp.next;//元素插入temp.next=list;}}public void addTwoOrderedList(SingleLinkedList otherList)//连接两个单链表{
//        boolean flag=false;LinkedList_ list=otherList.head.next;while(list!=null) {//其实就是先遍历要加入的链表LinkedList_ temp=this.head; //然后把这个链表按照add方法中添加到原先的单链表即可boolean flag=false;while (temp.next != null) {if (temp.next.data > list.data) {break;} else if (temp.next.data == list.data) {flag = true;break;}temp = temp.next;}if (flag) {System.out.println("当前元素已经存在");} else {//到这里说明list比temp.next小//使用clone方法是为了不让原有的list的指针域也被连接上去LinkedList_ newlist = (LinkedList_) list.clone();
//                LinkedList_ newlist=new LinkedList_(list.data,list.name);LinkedList_ next = temp.next;temp.next=newlist;newlist.next=next;}list=list.next;}}public void traverse()//遍历单链表{if(head.next==null){System.out.println("链表为空");return;}LinkedList_ temp=head;while(temp.next!=null){System.out.println(temp.next);temp=temp.next;}}public void update(LinkedList_ newlist)//根据newlist的data来修改{if(head.next==null){System.out.println("链表为空");return;}LinkedList_ temp=head;while(temp.next!=null){ //如果遇到了要删除的元素的data域if(newlist.data==temp.next.data){ //那么就修改其name域temp.next.name= newlist.name;}temp=temp.next; //不是就指向下一个元素}}public void delete(LinkedList_ dellist)//删除某个元素{if(head.next==null){ //先判断链表是否为空System.out.println("链表为空");return;}LinkedList_ temp=head;while(temp.next!=null){ //先判断下一个元素是否存在if(temp.next.equals(dellist)){ //存在后再判断是否是要删除的元素temp.next=temp.next.next;//如果是那么就直接让指针指向要删除元素的下一个元素break;  //之后只需要等待Java的垃圾回收机制来主动回收即可}temp=temp.next; //不是要删除的元素则指针向下}}public int getLength() //获取单链表长度{int size=0;LinkedList_ temp=head.next;while(temp!=null){size++;temp=temp.next;}return size;}public LinkedList_ getLastIndexNode(int lastIndex)//获取倒数第x个的数据元素{if(head.next==null||(this.getLength()<lastIndex)||lastIndex<0){System.out.println("链表为空/查询数据索引不合理");return null;}LinkedList_ temp=head.next; //第一个有效数据 去掉头指针int time=this.getLength()-lastIndex;//获取到这个元素需要遍历的次数for(int i=0;i<time;i++){temp=temp.next;}return temp;}public void reverseTraverse()//倒序遍历{//方法一 遍历链表并将数据加入到链表中去, 然后倒序输出链表
//        int i=this.getLength();
//        LinkedList_ temp=head;
//        LinkedList_[]listArr=new LinkedList_[i];
//        while(temp.next!=null){
//            listArr[--i]=temp.next;
//            temp=temp.next;
//        }
//        System.out.println(Arrays.toString(listArr));//方法二 直接遍历
//        for(int j=0;j<this.getLength();j++){
//            LinkedList_ temp=head;
//           for(int k=this.getLength();k>j;k--){
//               temp=temp.next;
//           }
//            System.out.println(temp);
//        }//方法三 使用栈Stack<LinkedList_> stack = new Stack<>();LinkedList_ temp=this.head.next;while(temp!=null){stack.add(temp);temp=temp.next;}while(stack.size()>0){System.out.println(stack.pop());}}public SingleLinkedList reverse()//反转{SingleLinkedList newlist=new SingleLinkedList();LinkedList_ cur = this.head.next; //第一个有效数据LinkedList_ temphead = newlist.head;LinkedList_ tempnext = null;//方法一 效率低的反转 但是原有单链表不会被破坏//方法一思路:两个for循环 外层for循环用于指明已经遍历了几个元素//内层for循环用于将元素指向待插入的最后一个元素//例如第一次外层for i=0 那么内层就需要进行最多次数的temp=temp.next;  ////那么就可以得到最后一个元素 第二次就可以得到倒数第二个元素 以此类推
//        int length = this.getLength();
//        for(int i=0;i<length;i++) { //length=6
//        LinkedList_ temp= this.head; //0 0 1 2 3 4 5
//            for(int j=length;j>i;j--) {
//                temp=temp.next;  //
//            }
//            temphead.next=temp.clone();
//            temphead=temphead.next;
//        }
//        temphead.next=null;//方法二 效率更高的反转 但是调用该函数的单链表将会被破坏while(cur!=null){tempnext=cur.next;cur.next=temphead.next;temphead.next=cur;cur=tempnext;}//方法三 按照方法一遍历 将遍历的元素存储到数组中去//然后倒序将数组的元素插入到新的链表即可return newlist;}
}
class LinkedList_ implements Cloneable{public int data;public String name;public LinkedList_ next;public LinkedList_(int data,String name) {this.data = data;this.name = name;}@Overridepublic LinkedList_ clone(){LinkedList_ temp=null;try {//如果该类没有实现CLoneable接口那么就会抛出异常temp = (LinkedList_)super.clone();//先拷贝父类中的基本消息\temp.next=null;//之后如果子类中有一些可变对象(如Date),那么就需要进行深拷贝//temp.date = (Date)new Date().clone();如下就} catch (CloneNotSupportedException e) {e.printStackTrace();}return temp;}@Overridepublic String toString() {return "LinkedList_{" +"data=" + data +", name='" + name + '\'' +'}';}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;LinkedList_ list = (LinkedList_) o;return data == list.data && Objects.equals(name, list.name) ;}@Overridepublic int hashCode() {return Objects.hash(data, name, next);}
}

总结

单链表由于数据不连续,且如果需要插入和删除元素只需要改变指针的指向,因此再插入和删除的时候效率相对于数组更高,但是由于数组可以直接使用索引访问元素,因此数组的元素访问效率更高.所以使用这两个数据结构应该对需求进行择优选择.