单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据域) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
头指针head和终端结点
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。
终端结点无后继，故终端结点的指针域为空，即NULL。
单链表的实现代码
项目目录结构
- 结构体 ListNode.java
- 接口类 MyList.java
- 实现类 SingleLinkedList.java
基本的结构体
ListNode.java:
package day01线性表;
/*单链表的实现*/
public class ListNode {
private Object data;//数据域
private Object next;//指针域
public ListNode(Object data) {
this.data = data;
}
// getter 和 setter 方法，对应着c语言中的结构体指针指向
// 也可以修改 data 和 next 两个成员变量的访问控制权限 ，直接通过 对象.成员变量来做
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Object getNext() {
return next;
}
public void setNext(Object next) {
this.next = next;
}
}
接口中的抽象方法
MyList.java:
package day01线性表;
public interface MyList {
/**
* 添加元素
* @param element
*/
void add(Object element);
/**
* 在指定位置插入元素
* @param target
* @param element
*/
void add(int target,Object element);
/**
* 根据元素的值来删除
* @param element
*/
void delete(Object element);
/**
* 根据索引来删除元素
* @param index
*/
void delete(int index);
/**
* 根据指定的target索引位置来更新元素
* @param traget
* @param element
*/
void update(int traget,Object element);
/**
* 返回某一元素第一次在线性表中出现的位置
* @param element
* @return
*/
int indexOf(Object element);
/**
* 返回在指定target位置的元素
* @param target
* @return
*/
Object elementAt(int target);
/**
* 取指定索引位置元素的前驱元素
* @param index
* @return
*/
Object elementPrior(int index);
/**
* 取指定索引位置元素的后继元素
* @param index
* @return
*/
Object elementNext(int index);
/**
* 是否包含某一元素
* @param element
* @return
*/
boolean contains(Object element);
}
实现类
SingleLinkedList.java:
package day01线性表;
import java.util.LinkedList;
public class SingleLinkedList implements MyList{
private ListNode head;//头节点
private ListNode last;//尾节点
private int size;//记录节点个数
@Override
public void add(Object element) {
if(head==null){
//一开始，头尾结点指向同一处
head = new ListNode(element);
last = head;
}else{
//尾插法
last.setNext(new ListNode(element));
//将 last 移动到自己的后继元素上
last = (ListNode) last.getNext();
}
size++;
}
@Override
public void add(int target, Object element) {
//这里这个指定位置插入，对于单链表意义不大，所以就忽略不写了
}
@Override
public void delete(Object element) {
//同样还是先记录头结点
ListNode p = head;
ListNode pre = null;//前驱节点一开始为空，方便后来的删除
// 因为单链表中的删除，就是将要删除的节点的前驱，直接指向要删除节点的后继节点
while (p!=null){
if(p.getData().equals(element)){
//如果删除的是头节点的值，那么就直接修改head指向即可
if(p==head){
head = (ListNode) head.getNext();
size--;
return;
}else {
// 删除节点的前驱指向删除节点的后继
pre.setNext(p.getNext());
size--;
return;
}
}
//没找到就一直往后面移动 pre 和 p
pre = p;
p = (ListNode) p.getNext();
}
//如果就是整个链表中都没找到则打印输出
System.out.println("当前链表中中不存在值为"+element.toString()+"的元素，无法删除!");
}
@Override
public void delete(int index) {
//index越界判断
if(index<0||index>=size){
System.out.println("要访问的索引已经越界!无法进行删除");
return;
}
int i = 0;//一开始头节点的索引为0
ListNode p = head;
ListNode pre = null;//头节点的前驱节点为空
while (p!=null){
if(i==index){
//如果删除的是头节点的值，那么就直接修改head指向即可
if(p==head){
head = (ListNode) head.getNext();
size--;
return;
}else {
// 删除节点的前驱指向删除节点的后继
pre.setNext(p.getNext());
size--;
return;
}
}
//没找到就一直往后面移动 pre 和 p
pre = p;
p = (ListNode) p.getNext();
i++;
}
}
@Override
public void update(int traget, Object element) {
//index越界判断
if(traget<0||traget>=size){
System.out.println("要访问的索引已经越界!无法进行修改");
return;
}
int i = 0;//一开始头节点的索引为0
ListNode p = head;
while (p!=null){
if(i==traget){
p.setData(element);
return;
}
//没找到就一直往后面移动 p
p = (ListNode) p.getNext();
i++;
}
}
@Override
public int indexOf(Object element) {
int i = 0;
ListNode p = head;
while(p!=null){
if(p.getData().equals(element)){
return i;
}
p = (ListNode) p.getNext();
i++;
}
return -1;//整个链表中并没有对应的元素，则返回-1
}
@Override
public Object elementAt(int target) {
if(target<0||target>=size){
System.out.println("索引越界,已经超过链表的元素个数");
return null;
}
int i = 0;
ListNode p = head;
while (p!=null) {
if (i == target) {
return p.getData();
}
p = (ListNode) p.getNext();
i++;
}
return null;
}
@Override
public Object elementPrior(int index) {
//索引越界
if(index-1<0||index>size){
return null;
}
int i =0;
ListNode p = head;
while (p!=null){
if (i==index-1){
return p.getData();
}
p = (ListNode) p.getNext();
i++;
}
return null;
}
@Override
public Object elementNext(int index) {
//索引越界
if(index<0||index+1>size){
return null;
}
int i =0;
ListNode p = head;
while (p!=null){
if (i==index+1){
return p.getData();
}
p = (ListNode) p.getNext();
i++;
}
return null;
}
@Override
public boolean contains(Object element) {
ListNode p = head;
while (p!=null){
if(p.getData().equals(element)){
return true;
}
p = (ListNode) p.getNext();
}
return false;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
ListNode p = head;
while (p!=null){
stringBuilder.append(p.getData());
if(p.getNext()!=null){
stringBuilder.append(",");
}
p = (ListNode) p.getNext();
}
stringBuilder.append("]");
return stringBuilder.toString();
}
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
list.add("e");
System.out.println(list);
list.delete("c");
System.out.println(list);
list.delete("a");
System.out.println(list);
list.delete("g");
list.update(0,"x");
System.out.println(list);
list.delete(0);
System.out.println(list);
list.delete(10);
list.update(3,"a");
list.add("a");
System.out.println(list);
list.contains("a");
System.out.println(list.elementAt(2));
System.out.println(list.indexOf(1));
System.out.println(list.indexOf("d"));
System.out.println(list.indexOf("e"));
list.add("b");
list.add("g");
System.out.println(list);
System.out.println(list.elementPrior(1));
System.out.println(list.elementNext(3));
System.out.println(list.elementNext(5));
}
}
这里mian方法最后的输出为：
线性表的总结
结合上一篇的顺序存储的总结java数据结构，线性表顺序存储（数组）的实现
- 对于顺序存储，按顺序放在一起，相邻元素通过内存地址相邻产生联系，”随机存取“。
- 而链式存储，元素随机放置在内存中任意位置，每个元素除了存放数据，也保存了其相邻元素的内存地址，来实现线性关系，“随机存取”。
- 单链表的存储空间会比相同元素个数的线性表多，原因是单链表中包括了数据域data和指针域next,所以其存储密度是小于1的。
对与线性表中的基本操作的时间复杂度
1.查找元素，按值查找。
- 给定长度为 n 的线性表，查找值为 v 的元素。(最坏)从头到尾遍历 => 时间复杂度O(n)
2.新增或者删除元素
- 对于顺序表来说，新增或者删除元素，需要对应的右移或者左移，最坏的情况是挪动所有元素的位置，时间复杂度为O(n)，空间复杂度为O(1).
- 对于单链表来说，新增或者删除元素，只需要修改前驱元素的next即可。因线性链表在插⼊或删除时，不需要移动元素，只要修改指针，⼀般情况下时间复杂度为O(1)。但是，如果要在单链表中进⾏前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。进⾏插⼊和删除的操作是常数即便，但是寻找前驱才要O(n)。空间复杂度为O(1).
3.更新元素
- 顺序表更新元素可以直接访问数组下标去进行修改，时间复杂度为O(1).
- 单链表则需从头节点开始遍历，最坏的情况是遍历整个链表，时间复杂度为O(n).
到此结束啦！java数据结构代码实现持续更新中!萌新学习笔记！
