一、前言
二、链表的简介
三、单向链表的API设置
代码实现
结点类:链表的设置结点类少不了
成员变量和构造方法
清空链表,链表的长度,链表是否为空
获取指定位置处的元素
插入元素t(在链表的最后以结点后插入元素)
在指定i处,添加元素t
删除指定位置i处的元素并返回被删除的元素
查找元素t在链表中第一次出现的位置
提供一个遍历的方法,实现Iterable接口
全部代码概览:
测试类下:
运行效果图:
四、鲁迅说:一个是关于head.next,另一个也是head.next
链表是一个和数组不一样的存储方式。我们都知道数组的存储地址是连续的,这样就不能很好的利
用好内存空间,而链表就解决了这个问题,链表是一存储地址不连续的的存储结构,这样的好处
就是能节省空间。
链表是由一系列的结点构成的,链表的第一个元素为头结点,头结点的特点是;不存放具体的数
表示单链表的表头,比如要找一个结点就是从头结点一个一个往下找的。
每一个结点有一个类似于指针的next,用来指向下一个结点,和一个date区域用于存储数据
头结点不存放数据,最后一个结点不指向null。
//定义节点类(成员内部类)
private class Node{
//存储数据
T item;
//下一个节点
Node next;
public Node(T item,Node next){
this.item=item;
this.next=next;
}
}
//记录头节点
private Node head;
//记录链表的长度
private int N;
//构造方法用来初始化成员变量
public LinkList(){
this.head=new Node(null,null);
this.N=0;
}
//方法1:清空链表
public void clear(){
head.next=null;//将头结点的指向置空
this.N=0;//元素个数变为0
}
//方法2:链表的长度
public int length(){
return N;//N就是链表长度
}
//方法3:判断链表是否为空
public boolean isEmpty(){
return this.N==0;//只需判断N是否为0即可
}
//方法4:获取指定位置处的元素
public T get(int i){
Node node=head.next;//node是下一个结点
if(node!=null){//有下一个结点
for(int index=0;index<i;index++){
node=node.next;//往下一个结点移动
}
return node.item;
}
return null;
}
//方法5:插入元素t(在链表的最后以结点后插入元素)
public void insert(T t){
//创建一个结点
Node node=head;
while(node.next!=null){//找到最后一个结点的前一个结点
node=node.next;
}
Node newLast=new Node(t, null);
//之前的最后指向现在的最后结点
node.next=newLast;
//元素个数加一
N++;
}
//方法6:在指定i处,添加元素t
public void insert(int i,T t){
//创建一个结点,从头结点开始
Node node =head;
for(int index=0;index<i;index++){//找到i位置处的前一个元素
node=node.next;
}
//当前i位置的结点
Node oldNode=node.next;
//创建结点t
Node newNode=new Node(t, null);
//此时node表示的还是前一个结点,所以只需要把前一个结点指向创建的新结点
node.next=newNode;
//新结点指向原来i位置处的结点,即可完成连接
newNode.next=oldNode;
//元素个数加一
N++;
}
//方法7:删除指定位置i处的元素并返回被删除的元素
public T remove(int i) {
//创建一个结点,从头节点开始
Node node=head;
//因为是从头结点开始的,所以下面循环会找到i位置的前一个结点
for(int index=0;index<i;index++){
node=node.next;
}
//i位置处的结点
Node iNode=node.next;
//直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点
node.next=iNode.next;//或者也可以node.next=node.next.next;
//元素减1
N--;
return iNode.item;
}
//方法8:查找元素t在链表中第一次出现的位置
public int indexOf(T t){
Node node=head;
for(int index=0;node.next!=null;index++){
node=node.next;
if(node.item.equals(t)){
return index;
}
}
//找不到
return -1;
}
public class LinkList<T> implements Iterable{}
//实现Iterable接口,重写iterator方法
@Override
//因为要的接口对象(接口不能直接new),所以我们必须创建一个对象去实现这个接口
public Iterator iterator() {
return new LIterator() ;
}
public class LIterator implements Iterator{
//实现Iterator接口重写hasNext()和next()两个方法
private Node n;
public LIterator(){
this.n=head;//从头结点开始
}
@Override
public boolean hasNext() {//是否有元素
return n.next!=null;
}
@Override
public Object next() {//返回下一个元素
n=n.next;
return n.item;
}
}
import java.util.Iterator;
public class LinkList<T> implements Iterable{
//定义节点类
private class Node{
//存储数据
T item;
//下一个节点
Node next;
public Node(T item,Node next){
this.item=item;
this.next=next;
}
}
//记录头节点
private Node head;
//记录链表的长度
private int N;
//构造方法用来初始化成员变量
public LinkList(){
this.head=new Node(null,null);
this.N=0;
}
//方法1:清空链表
public void clear(){
head.next=null;//将头结点的指向置空
this.N=0;//元素个数变为0
}
//方法2:链表的长度
public int length(){
return N;//N就是链表长度
}
//方法3:判断链表是否为空
public boolean isEmpty(){
return this.N==0;//只需判断N是否为0即可
}
//方法4:获取指定位置处的元素
public T get(int i){
Node node=head.next;//node是下一个结点
if(node!=null){//有下一个结点
for(int index=0;index<i;index++){
node=node.next;//往下一个结点移动
}
return node.item;
}
return null;
}
//方法5:插入元素t(在链表的最后以结点后插入元素)
public void insert(T t){
//创建一个结点
Node node=head;
while(node.next!=null){//找到最后一个结点的前一个结点
node=node.next;
}
Node newLast=new Node(t, null);
//之前的最后指向现在的最后结点
node.next=newLast;
//元素个数加一
N++;
}
//方法6:在指定i处,添加元素t
public void insert(int i,T t){
//创建一个结点,从头结点开始
Node node =head;
for(int index=0;index<i;index++){//找到i位置处的前一个元素
node=node.next;
}
//当前i位置的结点
Node oldNode=node.next;
//创建结点t
Node newNode=new Node(t, null);
//此时node表示的还是前一个结点,所以只需要把前一个结点指向创建的新结点
node.next=newNode;
//新结点指向原来i位置处的结点,即可完成连接
newNode.next=oldNode;
//元素个数加一
N++;
}
//方法7:删除指定位置i处的元素并返回被删除的元素
public T remove(int i) {
//创建一个结点,从头节点开始
Node node=head;
//因为是从头结点开始的,所以下面循环会找到i位置的前一个结点
for(int index=0;index<i;index++){
node=node.next;
}
//i位置处的结点
Node iNode=node.next;
//直接让i位置处的前以结点指向i位置的后一结点就可以删除i位置处的结点
node.next=iNode.next;//或者也可以node.next=node.next.next;
//元素减1
N--;
return iNode.item;
}
//方法8:查找元素t在链表中第一次出现的位置
public int indexOf(T t){
Node node=head;
for(int index=0;node.next!=null;index++){
node=node.next;
if(node.item.equals(t)){
return index;
}
}
//找不到
return -1;
}
//实现Iterable接口,重写iterator方法
@Override
//因为要的接口对象(接口不能直接new),所以我们必须创建一个对象去实现这个接口
public Iterator iterator() {
return new LIterator() ;
}
public class LIterator implements Iterator{
//实现Iterator接口重写hasNext()和next()两个方法
private Node n;
public LIterator(){
this.n=head;//从头结点开始
}
@Override
public boolean hasNext() {//是否有元素
return n.next!=null;
}
@Override
public Object next() {//返回下一个元素
n=n.next;
return n.item;
}
}
}
public class LinkListText {
public static void main(String[] args) {
//创建链表对象
LinkList<String> list=new LinkList<String>();
list.insert("张三");
list.insert("李四");
list.insert("王五");
list.insert("李四");
System.out.println("链表为空吗:"+list.isEmpty());
for(Object s:list){
System.out.println(s);
}
//元素个数
System.out.println("初始元素个数:"+list.length());
System.out.println("----------------------");
//插入
list.insert(1,"赵六");
list.insert(2,"历七");
//元素个数
System.out.println("插入后元素个数:"+list.length());
//第一次出现的位置
System.out.println("张三第一次出现的位置:"+list.indexOf("张三"));
System.out.println("----------------------");
for(Object s:list){
System.out.println(s);
}
//清除链表
list.clear();
System.out.println("清除后,链表为空吗:"+list.isEmpty());
}
}
有关于左右边的.next解读:
** 左边的.next表示的是指向,右边的.next表示的下一个元素。**
一般来说在左边的是指向,在右边的是下一个元素。(这里.next前可以是任意非null结点)
head.next!=null一样的道理。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_60719453/article/details/121706004
内容来源于网络,如有侵权,请联系作者删除!