一、链表是什么？
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
二、链表
1.链表的结构
链表的结构如图:
链表有8种结构:
1.单向带头循环 2.单向带头非循环. 3.单向不带头循环. 4.单向不带头非循环.
5.双向带头循环. 6.双向带头非循环. 7.双向不带头循环. 8.双向不带头非循环.
接下来介绍链表种主要的一些结构
1.单链表和双链表的结构如下:
2.不带头单链表丶带头单链表结构:
3.单链表丶循环单链表结构:
4. 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2.链表的方法代码实现
1.单链表实现方法:
1.我们先创建链表的val值和next
import java.util.Scanner; /** * Created with InteliJ IDEA. * /Description: * User:PANJIAPENG * Date:2022-08-11 * Time:9:20 */ //节点 class ListNode{ public int val; public ListNode next; public ListNode (int val){ this.val = val; } }
2.我们可以用最简单方法创建出一链表但是比较low,不建议使用,我们可以使用下面的头插法和尾插法来实现出链表
public class MylLnkedList { public ListNode head; //创建链表 low public void Mff(){ ListNode listNode1 = new ListNode(11); ListNode listNode2 = new ListNode(12); ListNode listNode3 = new ListNode(13); ListNode listNode4 = new ListNode(14); ListNode listNode5 = new ListNode(15); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; this.head = listNode1; }
3.打印链表:
//打印链表 public void display() { ListNode cur = this.head; while (cur != null) { System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); }
4.求链表的长度:
//求单链表长度 public int size(){ int count = 0; ListNode cur = this.head; while(cur != null){ count++; cur = cur.next; } return count; }
5.头插法:
//头插法 public void addFirst(int data){ ListNode node = new ListNode(data); if(this.head == null){ this.head = node; } else{ node.next = this.head; this.head = node; } }
6.尾插法:
//尾插法 public void addLast(int data){ ListNode node = new ListNode(data); ListNode cur = this.head; if(this.head==null){ this.head = node; } else{ while (cur.next != null){ cur = cur.next; } cur.next = node; } }
7.找到链表中是否有val值:
//找链表中是否有这个数 public boolean contains(int key){ ListNode cur = this.head; while(cur != null){ if(key == cur.val){ return true; } cur = cur.next; } return false; }
