线性表：零个或多个元素的有限序列；
线性表.jpg
线性表的顺序存储结构
线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。
package dataStructure;
//线性表顺序存储结构
public class SeqList<T>{
public static int MAXSIZE = 20; //存储空间初始分配量
private int length; //线性表当前长度
private T[] data; //数组存储数据元素
@SuppressWarnings("unchecked")
![Uploading 线性表_425942.jpg . . .]
public SeqList(){
data = (T[]) new Object[MAXSIZE];
}
//获取第i个元素
public T getElem(int i){
if(i<1 || i>getLength()){
return null;
}else{
return data[i-1];
}
}
//在位置i插入元素e
public boolean ListInsert(int i,T e){
//若顺序表已满
if(getLength() == MAXSIZE){
return false;
}
//i不在范围内
if(i<1 || i>getLength()+1){
return false;
}else{
//插入位置不在表尾
if(i<getLength()){
for(int j= getLength()-1;j>=i-1;j--){
data[j+1] = data[j];
}
}
data[i-1] = e;
setLength(getLength() + 1);
return true;
}
}
//删除第i个元素
public T ListDelete(int i){
//若表为空
if(getLength() == 0){
return null;
}
if(i<1 || i>getLength()){
return null;
}else{
T e = data[i-1];
//若不是最后一个
if(i<getLength()){
for(int j=i-1;j<getLength();j++){
data[j] = data[j+1];
}
}
setLength(getLength() - 1);
return e;
}
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
}
测试代码：
package dataStructure;
import java.util.Random;
public class SeqListTest {
final int MAX = 25;
Random r = new Random();
SeqList<Integer> seqList;
public SeqListTest() {
initSeqList();
}
//创建一个线性表顺序存储结构
public void initSeqList() {
seqList = new SeqList<Integer>();
// int length = (int) Math.random(); //只能产生0.0 - 1.0之间的double随机数
int length = Math.abs(r.nextInt(MAX)); //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值
System.out.println("产生的数组长度为 ：" + length);
if(length > SeqList.MAXSIZE) {
System.out.println("该长度不合法");
}
for (int i = 1; i <= length; i++) { //为生成的数组赋值，同时也测试了插入值的方法
int j =r.nextInt(MAX);
System.out.print(j + " ");
if(!seqList.ListInsert(i, j)) {
System.exit(0);
}
}
System.out.println("\n原始数组是 ：");
display(seqList);
}
//测试删除方法
public void deleteElem() {
int i = r.nextInt(MAX);
System.out.println("\n\n删除的位置是：" + i);
Integer deleteNumber = seqList.ListDelete(i);
if( deleteNumber == null) {
System.exit(0);
} else {
System.out.println("删除的元素是 ： " + deleteNumber);
System.out.println("删除元素后数组是 ：");
display(seqList);
}
}
//测试随机插入方法
public void insertByRandom() {
int i = r.nextInt(MAX);
System.out.println("\n\n随机插入位置是 ：" + i);
int elem = r.nextInt(MAX);
System.out.println("随机插入数据是 ：" + elem);
seqList.ListInsert(i, elem);
System.out.println("随机插入数据后数组是 ：");
display(seqList);
}
//数据展示
public void display(SeqList seqList) {
for (int i = 1; i <= seqList.getLength(); i++) {
if(seqList.getElem(i) != null) {
System.out.print(seqList.getElem(i) + " ");
}
}
System.out.println("数组的长度为 ：" + seqList.getLength());
}
//获取元素
public void getElem() {
int i = r.nextInt(MAX);
System.out.println("\n获取位置为 ：" + i);
System.out.println("获取到的元素为 : " + seqList.getElem(i));
}
public static void main(String[] args) {
SeqListTest s = new SeqListTest();
s.insertByRandom();
s.deleteElem();
s.getElem();
}
}
顺序存储优点：
1.无需为表示表中元素之间的逻辑关系而增加额外的存储空间。
2.对于存，读数据时时间复杂度都是O(1)。
顺序存储缺点：
1.插入和删除操作需要移动大量元素，时间复杂度为O(n)。
2.线性表长度变化较大时，无法确定存储空间的容量。
线性表的链式存储结构（单链表）
线性表的链式存储结构：用一组任意的存储单元存储线性表的数据元素。存储单元可以是连续的也可以是不连续的。
- 头指针：若有头结点，则指向头结点；否则是指向第一个结点。无论链表是否为空，头指针都不为空。
- 头结点：为了操作的方便而设立，在第一个元素之前。头结点的数据域不存储任何信息，指针指向第一个结点。若线性表为空，头结点的指针域为空。
- 最后一个结点指针为null
package dataStructure;
//链表中的结点node
public class Node<T>{
private T data; // 数据域
private Node<T> next;//指针域
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
}
package dataStructure;
public class LinkList<T>{
private Node<T> head;//头结点
private int length;//链表的长度
public LinkList(Node<T> head) {
this.head = head;
}
//获取第i个元素
public T getElem(int i){
int j = 1;
Node<T> n = head.getNext();//第一个元素
//得到第i个结点
while(n!=null && j<i){
n = n.getNext();
j++;
}
if(n == null || j>i){
return null;
}else{
return n.getData();
}
}
//在位置i之后插入e
public boolean ListInsert(int i,T e){
int j = 1;
Node<T> n = head;
//若为第一次插入
if(head == null && i==1){
head = new Node<T>();
head.setData(null);
Node<T> first = new Node<T>();
first.setData(e);
head.setNext(first);
length++;
return true;
}else{
//得到第i个结点
while(n!=null && j<i){
n = n.getNext();
j++;
}
if(n == null || j>i){
return false;
}else{
Node<T> s = new Node<T>();
s.setData(e);
s.setNext(n.getNext());
n.setNext(s);
length++;
return true;
}
}
}
//删除位置i
public T ListDelete(int i){
int j = 1;
Node<T> n = head.getNext();
//得到第i-1个结点
while(n!=null && j<i-1){
n = n.getNext();
j++;
}
if(n == null || j>i-1){
return null;
}else{
T e = n.getNext().getData();
n.setNext(n.getNext().getNext());
length--;
return e;
}
}
public Node<T> getHead() {
return head;
}
public void setHead(Node<T> head) {
this.head = head;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
}
测试代码：
package dataStructure;
import java.util.Random;
public class LinkListTest {
final int MAX = 25;
Random r = new Random();
LinkList<Integer> linkList;
public LinkListTest() {
initSeqList();
}
//创建一个线性表顺序存储结构
public void initSeqList() {
linkList = new LinkList<Integer>(null);
int length = Math.abs(r.nextInt(MAX)); //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值
System.out.println("产生的链表长度为 ：" + length);
for (int i = 1; i <= length; i++) { //为生成的链表赋值，同时也测试了插入值的方法
int j =r.nextInt(MAX);
System.out.print(j + " ");
if(!linkList.ListInsert(i, j)) {
System.exit(0);
}
}
System.out.println("\n原始链表是 ：");
display(linkList);
}
//测试删除方法
public void deleteElem() {
int i = r.nextInt(MAX);
System.out.println("\n\n删除的位置是：" + i);
Integer deleteNumber = linkList.ListDelete(i);
if( deleteNumber == null) {
System.exit(0);
} else {
System.out.println("删除的元素是 ： " + deleteNumber);
System.out.println("删除元素后链表是 ：");
display(linkList);
}
}
//测试随机插入方法
public void insertByRandom() {
int i = r.nextInt(MAX);
System.out.println("\n\n随机插入位置是 ：" + i);
int elem = r.nextInt(MAX);
System.out.println("随机插入数据是 ：" + elem);
linkList.ListInsert(i, elem);
System.out.println("随机插入数据后链表是 ：");
display(linkList);
}
//数据展示
public void display(LinkList<Integer> linkList) {
Node<Integer> node = linkList.getHead();
while(node != null) {
System.out.print(node.getData() + " ");
node = node.getNext();
}
System.out.println("链表的长度为 ：" + linkList.getLength());
}
//获取元素
public void getElem() {
int i = r.nextInt(MAX);
System.out.println("\n获取位置为 ：" + i);
System.out.println("获取到的元素为 : " + linkList.getElem(i));
}
public static void main(String[] args) {
LinkListTest s = new LinkListTest();
s.insertByRandom();
s.deleteElem();
s.getElem();
}
}
虽然已上所有链表的操作时间复杂度都为O(n),但如果在第i个位置插入10个结点这种操作，对于顺序存储结构是每次插入都要移动n-i个点，每次都是O(n)。但对于链式存储结构，只要在第一次通过O(n)找到位置i，那么接下来插如的操作时间复杂度都是O(1)。
因此，对于插入或删除数据越频繁的操作，单链表的效率优势越明显。
- 单链表的整表创建
package dataStructure;
public class CreateLinkList {
// 头插法创建长度为n的链表
public static LinkList<Integer> createListHead(int n) {
Node<Integer> head = new Node<Integer>();
LinkList<Integer> list = new LinkList<Integer>(head);
int j = 1;
// 将新结点插入到头结点与前一新结点之间
while (j <= n) {
Node<Integer> p = new Node<Integer>();
p.setData((int) (Math.random() * 25));
System.out.println(p.getData());
p.setNext(head.getNext());
head.setNext(p);
j++;
}
return list;
}
// 尾插法创建长度为n的链表
public static LinkList<Integer> createListTail(int n) {
Node<Integer> head = new Node<Integer>();
LinkList<Integer> list = new LinkList<Integer>(head);
int j = 1;
// 将结点插入到最后
while (j <= n) {
Node<Integer> p = new Node<Integer>();
p.setData((int) (Math.random() * 25));
System.out.println(p.getData());
head.setNext(p);
head = p;
j++;
}
return list;
}
// 数据展示
public static void display(LinkList<Integer> linkList) {
Node<Integer> node = linkList.getHead();
while (node != null) {
System.out.print(node.getData() + " ");
node = node.getNext();
}
}
public static void main(String args[]) {
display(createListHead(7));
}
}
- 单链表的整表删除
//整表删除
public void clearList(){
Node<T> p = head;
Node<T> q = new Node<T>();
while(q != null){
q = p.getNext();
if(q!=null){
p.setNext(q.getNext());
length--;
}
}
}
比较两种存储方式
Paste_Image.png
- 若线性表要频繁查找，很少进行插入和删除，宜使用顺序存储结构。反之宜用单链表结构。
- 当线性表中的元素个数变动较大或根本不知道有多大时，最好使用单链表。而如果事先知道线性表的大致长度，则考虑使用顺序结构。
静态链表
静态链表：用数组描述的链表。
每一个数组的元素有两个数据域：数据域与指针域（游标）。
package dataStructure.StaticLinkList;
public class Node<T>{
private T data;//数据域
private int cur;//指针域
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public int getCur() {
return cur;
}
public void setCur(int cur) {
this.cur = cur;
}
}
一般数组的第一个元素和最后一个元素会被作为特殊元素处理，不存数据。
通常把未被使用的数据元素成为备用链表。
- 数组的第一个元素的cur用来存放备用链表的第一个结点的下标。（即第一个没有数据的下标）
- 数组的最后一个元素的cur用来存放第一个有数值的元素的下标，相当于单链表中的头结点作用。
package dataStructure.StaticLinkList;
@SuppressWarnings("unchecked")
public class StaticLinkList<T> {
public static int MAXSIZE = 20;
private Node<T>[] list;
private int length;
public StaticLinkList(){
this.list = new Node[MAXSIZE];
}
// 初始化链表
public void initList() {
for (int i = 0; i < MAXSIZE; i++) {
Node<T> n = new Node<T>();
n.setCur(i+1);
list[i] = n;
}
// 目前静态链表为空，因此最后一个元素的cur为0
list[MAXSIZE-1].setCur(0);
}
// 在第i个元素位置插入e
public boolean ListInsert(int i, T e) {
//创建链表
if((length == 0 && i ==1)|| i == length+1){
list[i].setData(e);
list[MAXSIZE-1].setCur(1);
length++;
return true;
}
if (i < 1 || i > length) {
return false;
}
// 首先取得备用链表第一个结点的下标：
int cur = list[0].getCur();
// 同时改变第一个元素的cur，因为刚取出来的cur要被使用了，不再是备用链表的第一个结点了
list[0].setCur(list[cur].getCur());
list[cur].setData(e);
int k = MAXSIZE-1;
// 此时取出来的k为第i-1个元素的下标
for (int j = 1; j <= i - 1; j++) {
k = list[k].getCur();
}
// 第i个元素的下标
int insert = list[k].getCur();
list[k].setCur(cur);
list[cur].setCur(insert);
length++;
return true;
}
// 删除第i个元素
public T ListDelete(int i) {
if (i < 1 || i > length) {
return null;
}
int k = MAXSIZE-1;
// 此时取出来的k为第i-1个元素的下标
for (int j = 0; j < i - 1; j++) {
k = list[k].getCur();
}
//第i个元素下标：
int del = list[k].getCur();
T e = list[del].getData();
list[k].setCur(list[del].getCur());
//更改第一个元素的cur与要删除元素的cur，因为要删除的元素变成了备用链表的第一个元素
list[del].setCur(list[0].getCur());
list[0].setCur(del);
length--;
return e;
}
//展示数据
public void display(){
int k = list[MAXSIZE-1].getCur();
for(int i=1;i<=length;i++){
T e = list[k].getData();
k = list[k].getCur();
System.out.print(e + " ");
}
System.out.println("链表的长度为 ：" + getLength());
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
public Node<T>[] getList() {
return list;
}
public void setList(Node<T>[] list) {
this.list = list;
}
}
测试代码：
package dataStructure.StaticLinkList;
import java.util.Random;
public class StaticLinkListTest {
StaticLinkList<Integer> sllist = new StaticLinkList<Integer>();
// 用随机数初始化一个长度为n的静态链表
public void init(int n) {
sllist.initList();
for (int i = 1; i <= n; i++) {
sllist.ListInsert(i, (int) (Math.random() * 25));
}
display(sllist);
}
// 测试删除方法
public void deleteElem() {
int i = (int) (Math.random() * sllist.getLength());
System.out.println("\n\n删除的位置是：" + i);
Integer deleteNumber = sllist.ListDelete(i);
if (deleteNumber == null) {
System.exit(0);
} else {
System.out.println("删除的元素是 ： " + deleteNumber);
System.out.println("删除元素后链表是 ：");
display(sllist);
}
}
// 测试随机插入方法
public void insertByRandom() {
int i = (int) (Math.random() * sllist.getLength());
System.out.println("\n\n随机插入位置是 ：" + i);
int elem = (int) (Math.random() * 20);
System.out.println("随机插入数据是 ：" + elem);
sllist.ListInsert(i, elem);
System.out.println("随机插入数据后链表是 ：");
display(sllist);
}
// 展示list
public void display(StaticLinkList<Integer> sslist) {
sslist.display();
}
public static void main(String[] args) {
StaticLinkListTest s = new StaticLinkListTest();
s.init(8);
s.deleteElem();
s.insertByRandom();
}
}
- 静态链表优点：
在插入和删除时，只需改变游标而无需移动元素。 - 静态链表缺点：
没有解决连续存储分配内存空间难以确定的问题；
失去了顺序存储结构随机存取的特性。
循环链表
将单链表中的终端节点的指针由空指针改为指向头结点，就使得整个单链表形成一个环，这种头尾相接的单链表为循环链表。
循环链表解决了从任何一个结点出发从而遍历到所有结点的问题。
循环链表与单链表的主要差异：循环的判断条件，单链表是判断p.next是否为空，循环列表则判断p.next是否为头结点。
在单链表中，在访问尾结点时需要O(n)的时间。但如果在循环链表中不使用头指针，而是使用尾指针rear，则访问第一个结点和最后一个结点都是O(1)。
双向链表
在单链表的每个结点中，都有一个前驱指针指向其前驱结点。所以双向链表中的结点都有两个指针域，一个指向后继，一个指向前驱。
双向链表使得之前查前驱结点的时间复杂度由O(n)变为O(1)。
但双向链表在插入和删除时都需更改两个指针。
