Java数据结构---链表

目录

一、链表的概念和结构

1、概念

2、结构

二、链表的分类

三、链表的实现

1、创建节点类 

2、定义表头

3、创建链表

4、打印链表

5、链表长度

6、看链表中是否包含key

 7、在index位置插入val（0下标为第一个位置）

8、删除第一个关键字key

9、删除链表中所有key元素 

10、清空链表

 11、完整代码

---

一、链表的概念和结构

1、概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

2、结构

链表分为多个节点，每个节点可以由下图表示：

其中，value为这个节点所存储的数据的值，next为下一个节点的地址。以5个节点的链表为例，它们的数据值分别为12,23,34,45,56：

 

其中，第五个节点由于没有后继节点，所以next域存储的是空指针null。

二、链表的分类

链表的结构多种多样，按以下情况分类：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

共可分出8种类型。

三、链表的实现

本篇文章我们主要用代码实现无头单向非循环链表。

1、创建节点类 

static class ListNode{//ListNode为一个节点public int val;public ListNode next;public ListNode(int val) {//构造函数this.val = val;}
}

2、定义表头

    //定义表头public ListNode head;

3、创建链表

方法一：直接进行val的赋值和对next的初始化 

    public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(26);ListNode node3=new ListNode(30);ListNode node4=new ListNode(45);ListNode node5=new ListNode(56);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}

 方法二：头插法

    //头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}node.next=head;head=node;}

头插法是指在头节点的位置插入一个新节点。

    //尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}

尾插法是指在尾节点的位置插入一个新节点。

4、打印链表

    //打印链表public void show(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}

注意：为了使head在打印的过程中不受影响，我们可以重新定义一个cur，把head赋值给cur，这样head既不受影响，又可以继续下面的操作，两全其美。具体代码为：ListNode cur=head;，以下同理。

5、链表长度

    //链表长度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}

6、看链表中是否包含key

    //看链表中是否包含keypublic boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}

 7、在index位置插入val（0下标为第一个位置）

    //插入链表public void addIndex(int index,int val){if(index<0||index>size()){return;}if(index==0){addFirst(val);}else if(index==size()){addLast(val);}else{ListNode node=new ListNode(val);ListNode cur=findPindex(index);node.next=cur.next;cur.next=node;}}//找出index前一个节点private ListNode findPindex(int index){int i=1;ListNode cur=head;while(i<=index-1){cur=cur.next;i++;}return cur;}

 因为在插入之前需找出index的前一个节点，所以我们又创建了一个私有方法findPindex。

8、删除第一个关键字key

    //删除第一个出现的关键字keypublic void remove(int key){if(head==null){return;}if(head.val==key){head=head.next;}ListNode cur=findPkey(key);if(cur==null){return;}ListNode dve=cur.next;cur.next=dve.next;}//找出key前一个节点private ListNode findPkey(int key){ListNode cur=head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}

 因为在删除之前需找出key的前一个节点，所以我们又创建了一个私有方法findPkey。

9、删除链表中所有key元素 

    //删除链表中的所有key元素public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}

10、清空链表

    public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.next=null;cur=curN;}head=null;}

 11、完整代码

public class MySingleList {static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}//定义表头public ListNode head;//创建链表public void createList(){ListNode node1=new ListNode(12);ListNode node2=new ListNode(26);ListNode node3=new ListNode(30);ListNode node4=new ListNode(45);ListNode node5=new ListNode(56);node1.next=node2;node2.next=node3;node3.next=node4;node4.next=node5;this.head=node1;}//打印链表public void show(){ListNode cur=head;while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}//链表长度public int size(){ListNode cur=head;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}//看链表中是否包含keypublic boolean contains(int key){ListNode cur=head;while(cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}node.next=head;head=node;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;return;}ListNode cur=head;while(cur.next!=null){cur=cur.next;}cur.next=node;}//插入链表public void addIndex(int index,int val){if(index<0||index>size()){return;}if(index==0){addFirst(val);}else if(index==size()){addLast(val);}else{ListNode node=new ListNode(val);ListNode cur=findPindex(index);node.next=cur.next;cur.next=node;}}//找出index前一个节点private ListNode findPindex(int index){int i=1;ListNode cur=head;while(i<=index-1){cur=cur.next;i++;}return cur;}//删除第一个出现的关键字keypublic void remove(int key){if(head==null){return;}if(head.val==key){head=head.next;}ListNode cur=findPkey(key);if(cur==null){return;}ListNode dve=cur.next;cur.next=dve.next;}//找出key前一个节点private ListNode findPkey(int key){ListNode cur=head;while(cur.next!=null){if(cur.next.val==key){return cur;}cur=cur.next;}return null;}//删除链表中的所有key元素public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;ListNode prev=head;while(cur!=null){if(cur.val==key){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}if(head.val==key){head=head.next;}}public void clear(){ListNode cur=head;while(cur!=null){ListNode curN=cur.next;cur.next=null;cur=curN;}head=null;}
}

以上便是本篇文章的全部内容，感谢大家的支持！下期见~~~