文章目录
- 链表
- 1.链表的特点
- 2.链表的基础操作
- 2.1增
- 2.2删
- 3.自定义链表
- 3.1 自定义单向链表
- 3.2 自定义双向链表
链表
链表是一种常见的数据结构，由一系列节点构成，每个节点包含当前节点的数据和一个指针(单向链表)或者两个指针(双向链表)，链表是一种动态的数据结构，可以动态的增删节点。
1.链表的特点
-
逻辑结构：线性结构
-
物理结构：不要求连续的存储空间
-
存储特点：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在代码执行过程中动态创建。每个结点包括两个部分：一个是存储数据元素的
数据域，另一个是存储下一个结点地址的指针域。
2.链表的基础操作
2.1增
增加结点的逻辑是：将新增结点的指针域指向后一个结点，然后将原链表中的前一个结点的指针域指向新增的结点。(注意顺序不能颠倒，否则会导致插入位置后面的结点全部丢失)
//头插法
public void addFirst(int data){
Node node=new Node(data);
node.next=this.head;
this.head=node;
}
//尾插法
public void addLast(int data){
Node node=new Node(data);
Node cur=this.head;
if(this.head==null){
addFirst(data);
}else{
while (cur.next!=null){
cur=cur.next;
}
cur.next=node;
}
}
//给定位置插入
public boolean addIndex(int index,int data){
Node node=new Node(data);
Node cur=this.head;
if(index==0){
addFirst(data);
return true;
}else if(index==size()){
addLast(data);
return true;
}
if(index<0||index>size()){
System.out.println("插入位置不合法");
return false;
}
else{
for (int i = 0; i <index-1 ; i++) {
cur=cur.next;
}
//插入节点的尾指向下一个结点的头
node.next=cur.next;
//链表插入位置元素的下一个结点指向插入元素的头
cur.next=node;
}
return true;
}
2.2删
//删除第一次出现关键字为key的节点
public void remove(int key){
Node cur=this.head;
if(cur==null){
System.out.println("链表为空，删除错误");
return;
}else if(cur.val==key&&cur.next==null){
this.head=null;
return;
}else if(this.head.val!=key&&cur.next==null){
System.out.println("未找到key");
return;
}else if(this.head.val==key){
this.head=this.head.next;
return;
}
while (cur.next!=null){
if(cur.next.val==key){
cur.next=cur.next.next;
return;
}
cur=cur.next;
}
System.out.println("未找到key");
}
// 删除所有值为key的节点
public void removeAllKey(int key){
Node cur=this.head;
if(cur==null){
System.out.println("链表为空，删除错误");
}else if(cur.next==null&&cur.val==key){
this.head=null;
}else if(cur.next==null&&this.head.val!=key){
System.out.println("未找到key");
}else if(cur.val==key){
this.head=this.head.next;
}
while (cur.next!=null){
if(cur.next.val==key){
cur.next=cur.next.next;
continue;
}
cur=cur.next;
}
}
3.自定义链表
3.1 自定义单向链表
/*
单链表中的节点。
节点是单向链表中基本的单元。
每一个节点Node都有两个属性：
一个属性：是存储的数据。
另一个属性：是下一个节点的内存地址。
*/
public class Node {
// 存储的数据
Object data;
// 下一个节点的内存地址
Node next;
public Node(){
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
}
/*
链表类(单向链表)
*/
public class Link<E> {
// 头节点
Node header;
private int size = 0;
public int size(){
return size;
}
// 向链表中添加元素的方法（向末尾添加）
public void add(E data){
//public void add(Object data){
// 创建一个新的节点对象
// 让之前单链表的末尾节点next指向新节点对象。
// 有可能这个元素是第一个，也可能是第二个，也可能是第三个。
if(header == null){
// 说明还没有节点。
// new一个新的节点对象，作为头节点对象。
// 这个时候的头节点既是一个头节点，又是一个末尾节点。
header = new Node(data, null);
}else {
// 说明头不是空！
// 头节点已经存在了！
// 找出当前末尾节点，让当前末尾节点的next是新节点。
Node currentLastNode = findLast(header);
currentLastNode.next = new Node(data, null);
}
size++;
}
/**
* 专门查找末尾节点的方法。
*/
private Node findLast(Node node) {
if(node.next == null) {
// 如果一个节点的next是null
// 说明这个节点就是末尾节点。
return node;
}
// 程序能够到这里说明：node不是末尾节点。
return findLast(node.next); // 递归算法！
}
/*// 删除链表中某个数据的方法
public void remove(Object obj){
//略
}
// 修改链表中某个数据的方法
public void modify(Object newObj){
//略
}
// 查找链表中某个元素的方法。
public int find(Object obj){
//略
}*/
}
3.2 自定义双向链表
/*
双向链表中的节点。
*/
public class Node<E> {
Node prev;
E data;
Node next;
Node(Node prev, E data, Node next) {
this.prev = prev;
this.data = data;
this.next = next;
}
}
/**
* 链表类(双向链表)
* @author 尚硅谷-宋红康
* @create 15:05
*/
public class MyLinkedList<E> implements Iterable<E>{
private Node first; //链表的首元素
private Node last; //链表的尾元素
private int total;
public void add(E e){
Node newNode = new Node(last, e, null);
if(first == null){
first = newNode;
}else{
last.next = newNode;
}
last = newNode;
total++;
}
public int size(){
return total;
}
public void delete(Object obj){
Node find = findNode(obj);
if(find != null){
if(find.prev != null){
find.prev.next = find.next;
}else{
first = find.next;
}
if(find.next != null){
find.next.prev = find.prev;
}else{
last = find.prev;
}
find.prev = null;
find.next = null;
find.data = null;
total--;
}
}
private Node findNode(Object obj){
Node node = first;
Node find = null;
if(obj == null){
while(node != null){
if(node.data == null){
find = node;
break;
}
node = node.next;
}
}else{
while(node != null){
if(obj.equals(node.data)){
find = node;
break;
}
node = node.next;
}
}
return find;
}
public boolean contains(Object obj){
return findNode(obj) != null;
}
public void update(E old, E value){
Node find = findNode(old);
if(find != null){
find.data = value;
}
}
@Override
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E>{
private Node<E> node = first;
@Override
public boolean hasNext() {
return node!=null;
}
@Override
public E next() {
E value = node.data;
node = node.next;
return value;
}
}
}
自定义双链表测试：
package com.atguigu.list;
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList<String> my = new MyLinkedList<>();
my.add("hello");
my.add("world");
my.add(null);
my.add(null);
my.add("java");
my.add("java");
my.add("atguigu");
System.out.println("一共有：" + my.size());
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("查找java,null,haha的结果：");
System.out.println(my.contains("java"));
System.out.println(my.contains(null));
System.out.println(my.contains("haha"));
System.out.println("-------------------------------------");
System.out.println("替换java,null后：");
my.update("java","JAVA");
my.update(null,"songhk");
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
System.out.println("-------------------------------------");
System.out.println("删除hello，JAVA,null，atguigu后：");
my.delete("hello");
my.delete("JAVA");
my.delete(null);
my.delete("atguigu");
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
}
}
