一.链表的概念及结构
链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
value存数据,节点存下一个的地址,通过节点找下一个数据,每个节点都是一个对象
注意:
链式结构在逻辑上是连续的,但在物理上不一定连续】
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
链0pooooooooooooooooooo表有非常多种,以下情况组合起来就有八种链表结构
1.单向或双向
2.带头或不带头
3.循环或非循环
我们重点掌握两种
1.无头单向非循环列表:结构简单,一般不用来单独存数据,更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等等
2.无头双向链表:在Java的框架中,LinkedList底层实现就是无头双向循环链表
二.链表的实现
1.简单创建
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(23);
ListNode node3 = new ListNode(34);
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;
}
}
2.遍历链表
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
注意head不能丢
3.得到单链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
4.查找关键字key是否在单链表中
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
5.头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
6.尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
ListNode cur = head;
if(cur == null) {
head = node;
return;
}
//找到链表的尾巴 注意是cur.next 不是cur
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
7.任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
if(index < 0 || index > size()) {
System.out.println("index 不合法");
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
ListNode cur = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
/**
* 找到要删除节点位置的前一个节点
* @param index
* @return
*/
private ListNode findIndexSubOne(int index) {
ListNode cur = head;
while (index-1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
8.删除第一次出现关键字为key的节点
public void remove(int key){
if(head == null) {
return;
}
//单独删除头节点
if(head.val == key) {
head = head.next;
return;
}
ListNode cur = searchPrev(key);
if(cur == null) {
System.out.println("没有你要删除的数字");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
/**
* 找到关键字 key的前驱
* @param key
* @return
*/
private ListNode searchPrev(int key) {
ListNode cur = head;
while (cur.next != null) {
if(cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
9.删除所有值为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() {
this.head = null;
}