1.??链表的概念及结构
? ? ? ?链表是一种
物理存储结构上非连续
存储结构，数据元素的
逻辑顺序
是通过链表中的
引用链接
次序实现的 。
实际中链表的结构非常多样，以下情况组合起来就有
8
种链表结构：
1.
单向或者双向
2.
带头或者不带头
3.
循环或者非循环
那么组合起来就有8种结构,
虽然有这么多的链表的结构，但是我们重点掌握两种:?无头单向非循环链表 ,无头双向链表
2. 链表的实现
// 1、无头单向非循环链表实现
public class SingleLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
//打印整个链表
public void display();
//清空整个链表
public void clear();
}1. 创建一个链表
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
public void createList(){
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
?2. 打印链表的所有元素:
public void display(){
if (this.head == null) {
return ;
}
ListNode ret = this.head;
while (ret != null){
System.out.println(ret.val+" ");
ret = ret.next;
}
}?
3. 输出链表的长度
public int size(){
int usedsize = 0;
ListNode ret = this.head;
while (ret != null){
usedsize ++;
ret = ret.next;
}
return usedsize;
}
?
?4. 查找是否包含关键字key在单链表中
public boolean contains(int key){
ListNode ret = this.head;
while (ret != null){
if (ret.val == key) {
return true;
}
ret = ret.next;
}
return false;
}
?5. 头插法插数据元素
public void addFirst(int data){
ListNode node = new ListNode(data);//给一个节点
if (this.head == null) {//空链表
this.head = node;
}else {
node.next = this.head;
head = node;
}
}
?6.尾插法插入数据元素
public void addLast(int data){
ListNode node = new ListNode(data);
ListNode ret = this.head;
if (this.head == null){
this.head = node;
}
while (ret.next != null){
ret = ret.next;
}
ret .next = node;
}
?7. 任意位置插入节点
//任意位置插入
public void addIndex(int index,int data) {
if (index < 0 || index > size()) {
System.out.println("index 不合法!");
throw new IndexWrongFullExcept("index 位置不合法!");
}
if (index == 0) {//相当于头插法
addFirst(data);
return;
}
if (index == size()) {//相当于尾插法
addLast(data);
return;
}
//插入节点
ListNode ret = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = ret.next;
ret.next = node;
}
//先走index-1步,找到ret
private ListNode findIndexSubOne(int index){
ListNode ret = this.head;
while (index - 1 != 0){
ret = ret.next;
index --;
}
return ret;
}
?8. 删除第一次出现的key的节点
public void remove(int key) {
if (this.head == null) {
return;
}
if (this.head.val == key) {
this.head = head.next;
return;
}
ListNode ret = findPrevOfKey(key);
ListNode del = ret.next;
if (ret == null) {
System.out.println("没有找到要删除的数字!");
return;
} else {
ret.next = del.next;
}
}
//找到要删除的节点的前一个节点
private ListNode findPrevOfKey(int key){
ListNode ret = this.head;
while (ret.next != null){
if (ret.next.val == key) {
return ret;
}
ret = ret.next;
}
return null;
}
9. 删除所有值为key的节点
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode ret = this.head.next;
ListNode prev = this.head;
while (ret != null){
if (ret.val == key){
prev.next = ret.next;
ret = ret.next;
}
else {
prev = ret;
ret = ret.next;
}
}
if (this.head.val == key){
this.head = head.next;
}
}
?
10. 清空整个链表
这个很简单 我们让我们的头节点直接变成空的,是不是就清空了
//清空整个链表
public void clear(){
this.head = null;
}?3. 自己实现一个链表的全部代码
public class MySingleList {
//内部类表示一个节点
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//头节点
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);//给一个节点
if (this.head == null) {//空链表
this.head = node;
} else {
node.next = this.head;
head = node;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
ListNode ret = this.head;
if (this.head == null) {
this.head = node;
}
while (ret.next != null) {
ret = ret.next;
}
ret.next = node;
}
//任意位置插入
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
System.out.println("index 不合法!");
throw new IndexWrongFullExcept("index 位置不合法!");
}
if (index == 0) {//相当于头插法
addFirst(data);
return;
}
if (index == size()) {//相当于尾插法
addLast(data);
return;
}
//插入节点
ListNode ret = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = ret.next;
ret.next = node;
}
//先走index-1步,找到ret
private ListNode findIndexSubOne(int index) {
ListNode ret = this.head;
while (index - 1 != 0) {
ret = ret.next;
index--;
}
return ret;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode ret = this.head;
while (ret != null) {
if (ret.val == key) {
return true;
}
ret = ret.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
if (this.head == null) {
return;
}
if (this.head.val == key) {
this.head = head.next;
return;
}
ListNode ret = findPrevOfKey(key);
ListNode del = ret.next;
if (ret == null) {
System.out.println("没有找到要删除的数字!");
return;
} else {
ret.next = del.next;
}
}
//找到要删除的节点的前一个节点
private ListNode findPrevOfKey(int key){
ListNode ret = this.head;
while (ret.next != null){
if (ret.next.val == key) {
return ret;
}
ret = ret.next;
}
return null;
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode ret = this.head.next;
ListNode prev = this.head;
while (ret != null){
if (ret.val == key){
prev.next = ret.next;
ret = ret.next;
}
else {
prev = ret;
ret = ret.next;
}
}
if (this.head.val == key){
this.head = head.next;
}
}
//得到单链表的长度
public int size(){
int usedsize = 0;
ListNode ret = this.head;
while (ret != null){
usedsize ++;
ret = ret.next;
}
return usedsize;
}
//打印列表当中的元素
public void display(){
if (this.head == null) {
return ;
}
ListNode ret = this.head;
while (ret != null){
System.out.print(ret.val+" ");
ret = ret.next;
}
}
//清空整个链表
public void clear(){
this.head = null;
}
//创建链表
public void createList(){
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(12);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(12);
ListNode listNode5 = new ListNode(12);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
}那么本次链表的分享就到此结束了,下次再见