1.链表的概念:

2.链表的结构:

(1)单向列表或双向列表：

(2).带头或者不带头节点:

(3). 循环或者非循环:

但今天我们重点讲解无头单向非循环链表：结构简单.

链表的实现:

1.无头单向非循环列表的实现：

1.1确定实现的功能并这些功能放入接口中：

我们实现的单链表功能有：头插（addFirst），尾插(addLast)，展示(display）,链表大小(size),    是否包含所需的值(contain), 指定位置插入元素（index）, 移除指定元素(remove)，将其放入接口中即可

public interface IList {//头插法public void addFirst(int data);//尾插法public void addLast(int data);//遍历展示public void disPlay();//得到链表的大小？public int size();//判断链表中是否包含所需的值public boolean contains(int key);//在指定位置插入元素public void index(int index,int data);//移除指定元素public void remove(int key);//清空与key相同的链表public void removeAllKey(int key);//qingli'public void clear();}

1.2基本结构的实现:

(1).定义链表结构：数据域和指向下一节点的指针，创建接受收数据域的构造方法，同时也要包含头指针(head)，具体代码实现如下：

static class ListNode{public int val;public ListNode next;public ListNode(int val){this.val = val;}}public ListNode head;

（2）创建链表：

创建5个节点并随机赋值，通过指针将5个节点连接起来。具体代码如下：

 public void creatList(){ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(25);ListNode node3 = new ListNode(26);ListNode node4 = new ListNode(30);ListNode node5 = new ListNode(33);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;//this.node = node;}

1.3基本功能的实现:

(1) display()

创建一个指针cur指向头节点，    while循环cur不为空时，打印对应的值，同时指针指向下一个节点具体代码如下：

 public void disPlay(){ListNode cur = head;while(cur!=null){System.out.println(cur.val+" ");cur = cur.next;}System.out.println();}

（2） size（链表大小）

创建一个cur指针，指向链表头节点head，同时创建一个整形len，while每次循环cur指针不为空，

则len自增1，同时指针指向下一个节点，循环结束返回len，具体代码如下:

public int size() {int len = 0;ListNode cur = head;while(cur!=null){len++;cur = cur.next;}return len;}

(3) contain:

遍历头节点cur，若cur的值==key，则返回true，同时指向下一个节点，否则false，

具体代码如下：

  public boolean contains(int key){ListNode cur = head;  //创建头节点while(cur!=null)    //循环遍历cur的值是否等于key{if(cur.val == key){return true;}cur = cur.next;   //地址自增}return false;}

（4）addFirst（头插）

新创一个节点，将新创节点的指针域传给头节点，同时将node转变为头节点：

具体代码如下：

 public void  addFirst(int data){ListNode node  = new ListNode(data);node.next = head;head = node;  //新创节点变为头节点}

(4)尾插：

创建一个node节点，将data放入：

判断head头节点是否为空，为空，则为空链表，这时插入的节点既是头节点也是尾节点，将node转为头节点。

head不为空，通过while循环cur.next !=null（判断是否到达尾节点），没到达，cur节点继续往下走，到达了，把cur.next节点指向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;}

(5) 指定位置插入元素：

通过size方法获取链表长度并赋值给变量len,若索引index<0或index>len,此时位置不合法，需返回。

当index == 0,头插即可

当index == len,尾插即可

其余情况，举了个例子，如下，你想在2位置插入新值，就要获取1位置的节点，即index-1位置上的节点，创建一个cur节点来接收头节点，此时可以通过index-1!=0作为while循环条件，每次将cur自增1，将index自减1，让cur达到index-1的位置

这里将新节点的 next 指向当前节点 cur 的下一个节点，然后将 cur 的 next 更新为新节点，从而实现插入

以上就是今天要分享的知识点，喜欢的老铁来个三联把！