JAVA数据结构——单链表

链表：一、顺序存储结构虽然是一种很有用的存储结构，但是他有如下几点局限性：
1. 因为创造线性表的时候已经固定了空间，所以当需要扩充空间时，就需要重新创建一个地址连续的更大的存储空间。并把原有的数据元素复制进新的存储空间。
2. 因为顺序表要求数据的存储位置不仅是逻辑上相邻而且物理存储上也要相邻，所以当对数据进行增删操作的时候则会引起平均一半的数据元素移动。
综上所述：适合静态存储、对数据元素很少增删操作，则优先选择顺序表，对需要对数据频繁执行插入和删除操作，则选择动态的线性表-链表，链式存储不需要逻辑上相邻的元
素物理上也相邻，所以链表也带来了一定的局限性，失去了随机存取的特点。所以根据需求进行选择。
二、使用JAVA实现单链表:接口同顺序表：

[Java] 纯文本查看复制代码

package com.usts.edu.list;

/**

* Created by Guanzhong Hu

* Date :2019/12/27

* Description : 线性表

* Version :1.0

*/

public interface Ilist {

// 将已存在的线性表置空

public void clear();

// 判断是否为空

public boolean isEmpty();

// 求线性表中数据元素个数并返回其值

public int length();

// 读取第i个元素的值区间：[0，length()-1]

public Object get(int i) throws Exception;

//    插入元素，i表示插入的地址取值 区间：[0，length()-1]，当为length()-1时，表示在表尾插入x

public void insert(int i,Object x) throws Exception;

// 删除位于第i个的元素

public void remove(int i) throws Exception;

// 返回线性表中元素第一次出现的index

public int indexOf(Object x) throws Exception;

// 输出线性表中各个数据元素的值

public void display();

}

[Java] 纯文本查看复制代码

package com.usts.edu.list;

/**

* Created by Guanzhong Hu

* Date :2019/12/27

* Description :单链表

* Version :1.0

*/

public class Node {

/**

* 采用链式存储方式存储的线性表成为单链表

* 1. 链表中每一个结点包含存放数据元素值的数据域和存放指向逻辑上相邻结点的指针域

* 2. 若节点中只包含一个指针域，则称此链表为单链表

*/

public Object data;//存放结点值

public Node next; // 存放逻辑指针

public Node(){

this(null,null);// 置空

}

// 两个参数的单链表

public Node(Object data, Node next) {

this.data = data;

this.next = next;

}

// 带一个参数的单链表

public Node(Object data){

this(data,null);

}

[Java] 纯文本查看复制代码

001

002

003

004

005

006

007

008

009

010

011

012

013

014

015

016

017

018

019

020

021

022

023

024

025

026

027

028

029

030

031

032

033

034

035

036

037

038

039

040

041

042

043

044

045

046

047

048

049

050

051

052

053

054

055

056

057

058

059

060

061

062

063

064

065

066

067

068

069

070

071

072

073

074

075

076

077

078

079

080

081

082

083

084

085

086

087

088

089

090

091

092

093

094

095

096

097

098

099

100

101

102

103

104

105

106

107

108

109

110

111

112

113

package com.usts.edu.list;

import java.math.BigInteger;

import java.util.Scanner;

/**

* Created by Guanzhong Hu

* Date :2019/12/27

* Description :实现单链表

* Version :1.0

*/

public class LinkList implements Ilist {

private Node head;

public LinkList() {

head = new Node();// 生成空的单链表

}

// 置空

@Override

public void clear() {

head.data = null;

head.next = null;

}

@Override

public boolean isEmpty() {

return head.next==null; // 头指针为null，则空

}

@Override

public int length() {

int length = 0;// 初始化length

Node n = head.next; // 初始化头指针，进行遍历

while (n != null){

n = n.next; // 迭代遍历

length++;

}

return length;

}

@Override

public Object get(int i) throws Exception {

Node n = head.next;

int flag = 0;

// 初始化查找参数，依次遍历寻找，当存在下一个头指针且flag = i时，则返回当前指针指向的下一个元素

while (n != null && i > flag){

n = n.next;

flag++;

}

if (n==null|| i<flag){

throw new Exception("查找的第"+i+"个元素不存在！");

}

return n.data;

}

@Override

public void insert(int i, Object x) throws Exception {

Node p = head;

int flag = -1; // 定义计数器，从-1开始，因为第一个元素的头指针是-1；

while (p!=null&&flag<i-1){ //寻找第i个结点的前驱，如果前驱小于则可以插入，否则当前元素位置已经占

p = p.next;// 已经指向当前结点的位置，需要后期插入成功后，指向下一个结点位置

flag++;

}

if (p==null&&flag>i-1) throw new Exception("插入位置不合法");

Node newNode = new Node(x);

newNode.next = p.next; // 指向下一个结点位置

p.next = newNode;

// 将当前生成的结点(下一个结点指针，当前节点元素)存入p的上一个结点的下一个结点的指针中

}

@Override

public void remove(int i) throws Exception {

Node p = head;

int flag = -1; // 同上

while (p!=null&&flag<i-1){

p = p.next;

flag ++;

}

if (p==null&&flag>i-1) throw new Exception("删除位置不合法");

p.next = p.next.next;// 将此节点的上一个节点的指针指向当前删除节点的下一个结点

}

@Override

public int indexOf(Object x) throws Exception {

Node p = head;

int flag = -1;

while (p!=null&&p.data.equals(x)){

p = p.next;

flag ++;

}

if (p!=null) return flag;

return -1;

}

@Override

public void display() {

Node p = head.next;

// 如果指针含有下一个元素，则输出，并替换查询指针

while (p!=null){

System.out.print(p.data);

p = p.next;

}

System.out.println();

}

//创建链表,测试使用

public void createLinkList(int len) throws Exception{ // 头插法，创建len长度的链表

Scanner scanner = new Scanner(System.in);

for (int i = 0; i < len ; i++) {

insert(0,scanner.next());

}

[Java] 纯文本查看复制代码

package com.usts.edu.list;

import java.util.Scanner;

/**

* Created by Guanzhong Hu

* Date :2019/12/27

* Description : 测试单链表

* Version :1.0

*/

public class ExampleLinkListTest {

public static void main(String[] args) throws Exception {

int len = 10;

LinkList linkList = new LinkList();

// 利用for生成链表

for (int i = 0; i < len ; i++) {

linkList.insert(i,i);

}

System.out.println("请输入查找的值");

int i = new Scanner(System.in).nextInt();

if (i>0&&i<=len) System.out.println("第"+i+"个元素的直接前驱"+linkList.get(i-1));

linkList.display();

linkList.clear();

linkList.display();

linkList.insert(0,1);

秒客网

JAVA数据结构——单链表

相关文章