【数据结构和算法】链表实现
【摘要】 目录一、前言二、链表的简介三、单向链表的API设置 代码实现结点类：链表的设置结点类少不了 成员变量和构造方法 清空链表，链表的长度，链表是否为空 获取指定位置处的元素 插入元素t(在链表的最后以结点后插入元素) 在指定i处，添加元素t 删除指定位置i处的元素并返回被删除的元素 查找元素t在链表中第一次出现的位置提供一个遍历的方法，实现Iterable接口全部代码概览：测试类下：运行效果...
目录
四、鲁迅说：一个是关于head.next，另一个也是head.next
一、前言
链表是一个和数组不一样的存储方式。我们都知道数组的存储地址是连续的，这样就不能很好的利
用好内存空间，而链表就解决了这个问题，链表是一存储地址不连续的的存储结构，这样的好处
就是能节省空间。
二、链表的简介
链表是由一系列的结点构成的，链表的第一个元素为头结点，头结点的特点是；不存放具体的数
表示单链表的表头，比如要找一个结点就是从头结点一个一个往下找的。
每一个结点有一个类似于指针的next，用来指向下一个结点，和一个date区域用于存储数据
头结点不存放数据，最后一个结点不指向null。
三、单向链表的API设置
代码实现
结点类：链表的设置结点类少不了
//定义节点类(成员内部类)
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;
}插入元素t(在链表的最后以结点后插入元素)
//方法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++;
}在指定i处，添加元素t
//方法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++;
}删除指定位置i处的元素并返回被删除的元素
//方法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;
}查找元素t在链表中第一次出现的位置
//方法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接口
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());
}
}
运行效果图：
四、鲁迅说：一个是关于head.next，另一个也是head.next
有关于左右边的.next解读：
左边的.next表示的是指向，右边的.next表示的下一个元素。
一般来说在左边的是指向，在右边的是下一个元素。（这里.next前可以是任意非null结点）
head.next!=null一样的道理。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）