java之单链表的基本概念及创建
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 更新为新节点，从而实现插入
以上就是今天要分享的知识点，喜欢的老铁来个三联把！