线性表
#学习目标
- 掌握线性表基础思想、优缺点、常见分类，能复述；
- 能使用
java代码实现线性表创建，元素插入、删除、元素修改、查找； - 完成一道相关题目。
#基础思想、优缺点
1.基础思想
在内存中可以非连续存储，提高空间利用率，理论上其大小是内容能使用空间的大小（非连续）；
2.优缺点
优点：
- 空间无限制
- 插入元素、删除元素很快
缺点：
查找速度很慢。
#常见分类
**单向链表：**一个节点只指向下一个节点
**双向链表：**一个节点同时包含下一个节点和上一个节点的引用（指针）
**环形链表：**链表首位相连（单、双链表均可），从任何一个节点可以遍历整个链表
#实现
1.节点：包含下一个节点域、数据域
/**
* 链表节点
* @author PIZIWANG
* @date 2022-04-28 17:33
**/
public class SingleNode {
int data;
SingleNode next;
public SingleNode(){}
public SingleNode(int data){
this.data = data;
}
public SingleNode(int data,SingleNode next){
this.data = data;
this.last = next;
}
}
package com.piziwang.linkedlist;
/**
* 链表
* @author PIZIWANG
* @date 2022-04-28 20:44
**/
public class MyLinkedList{
SingleNode first;
SingleNode last;
int size;
}
后面方法均是MylinkedList方法
2.插入节点
/**
* 添加元素
* @param value 值
*/
public void add(int value){
SingleNode l = last;
SingleNode newNode = new SingleNode(value);
last = newNode;
// 如果链表为空
if(l == null){
first = newNode;
}else {
l.netx = newNode;
}
size++;
}
3.遍历
/**
* 打印链表-->循环
*/
public void print(){
SingleNode node = first;
while (node != null) {
System.out.print(node.data);
node = node.next;
if (node != null) {
System.out.print("-->");
}
}
System.out.println();
}
需要改
MylinedList类，实现Iterable接口
/**
* 打印链表-->for
*/
for(Object o : list){
System.out.println(o);
}
package com.piziwang.linkedlist;
/**
* 链表
* @author PIZIWANG
* @date 2022-04-28 20:44
**/
public class MyLinkedList implements Iterable{
SingleNode first;
SingleNode next;
int size;
/**
* 迭代器，实现for遍历打印
* @return {@link Iterator}
*/
@Override
public Iterator iterator() {
return new Iterator() {
SingleNode node = first;
@Override
public boolean hasNext() {
return node != null;
}
@Override
public Object next() {
int value = node.data;
node = node.next;
return value;
}
};
}
}
4.查找
/**
* 获取元素在链表中的位置
* @param value
* @return
*/
public int getIndex(int value){
SingleNode current = first;
int index = 0;
while (index<size) {
if (current.data == value) {
return index;
}
current = current.next;
index ++;
}
return -1;
}
/**
* 获取指定索引出的元素值
* @param index 指数
* @return int
*/
public int getValue(int index){
checkElementIndex(index);
return node(index).data;
}
/**
* 检查元素索引
* @param index 指数
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 双向链表看离first近还是离last近，然后从一端查
* @param index
* @return
*/
SingleNode node(int index) {
// 离first近
SingleNode x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
5.清空
/**
* 清空所有元素
*/
public void clear(){
for (SingleNode x = first; x != null; ) {
SingleNode next = x.next;
x.setData(0);
x.next=null;
x = next;
}
first = last = null;
size = 0;
}
6.求长度
/**
* 获取链表长度
*
*/
public int size() {
return size;
}
7.删除节点
/**
* 删除指定元素节点
* 没有办法知道前一个节点，只需要把后续节点拷贝到当前节点即可
*/
public boolean remove(int value){
for(SingleNode x = first;x != null; x = x.next){
if (x.data == value) {
x.data=x.next.data;
x.next=x.next.next;
}
}
return false;
}
