1、顺序表的存储结构（定义类的成员变量）
//顺序表的初始化
public SequenceList<T>{final int defaultSize=10;//顺序表中一维数组的初始容量T[]listArray;//存储元素的数组int length;//当前元素的实际个数
//（1）顺序表的初始化：创建一个空的顺序线性表，即给成员变量赋初值
public SequenceList(int n){if(n<0){System.out.println("error!")System.exit(1);this.listArray=(T[])new Object[n];//创建容量为n的数组this.length=0;//存储的元素个数为0}
}
public SequenceList<T>{ //创建默认容量的空顺序表T[]listArray=(T[])new Object[defaultSize];this.length=0;}
}(2)插入操作（在第pos个位置插入元素obj）
步骤：①插入元素合法性判断（1<=pos<=this.length+1）
②是否需要追加空间
③An-Apos后移一个位置（下标为pos-1）
④表长加1
操作特点：插入位置后面的元素均需要后移一个位置
public boolean add(T obj,int pos){//在顺序表的第pos个位置之前插入新的数据e，pos的合法值为1-ListLength（l）+1，返回true，若i值不合法，返回false；
if(pos<1||pos>this.length+1){ //pos代表的是元素的位置，不是元素的下标索引System.out.println("pos值不合法");return false;}
} if(this.length==this.listArray.length) { //当前存储空间已满，增加分配
//如果当前存储的元素个数等于数组的长度，则需要扩容T[] p= (T[])new Object[this.length * 2];for(int i=0; i<this.length; i++) p[i] = this.listArray[i]; //移动元素至新数组中this.listArray=p;} //end if
for(int i=this.length-1; i>=pos-1; i--)
//位置pos(下标pos-1)之后的元素均后移一个位置this.listArray[i+1] = this.listArray[i];this.listArray[pos-1]= obj; //obj放入第pos个单元（下标pos-1）this.length++; //表长加1return true;
}
时间复杂度分析：
l 基本操作：移动元素l 基本操作至少执行次数： 0 次（在表尾插入时）l 基本操作至多执行次数： n 次（在表首插入时）l 基本操作平均执行次数：（ n+(n-1)+……+0 ） / （ n+1 ） =n/2l 时间复杂度： O(n)
（3）删除操作
步骤：判断删除位置pos合法性（1<= pos <= this.length）
将ai赋值给x
apos+1—an向前移动一个位置
表长减1
返回x
操作特点：删除位置之后的元素均需前移一个位置
public T remove(int pos)
{ //在顺序表中删除第pos个元素并返回其值，pos的合法值为1<=pos<=this.lengthif(length==0){ //空表
system.out.println(“顺序表为空，无法执行删除操作”);
return null; }
if(pos<1||pos>this.length) //pos值不合法,返回null
system.out.println(“pos值不合法”);
return null; }T x = this.listArray[pos-1];for(int i=pos; i<this.length; i++)this. listArray[i-1] = this. listArray[i]; //被删除元素之后的元素向前移一个位置this.length--; //表长减1return x；
} //ListDelete_Sq基本操作：元素移动
最好情况下移动元素的次数：0次（删除表尾元素时）
最坏情况下移动元素的次数：n-1次（删除表首元素时）
平均移动元素的次数：
时间复杂度：O(n)
（4）查找操作（查找和元素obj相等的元素，返回其位序，若不存在返回0）
public int find(T obj)
{ //查找第1个与obj相等的元素的位序，返回其位序，若不存在则返回0。for(i=0;i<this.length;i++) if(obj.equals(this.listArray[i]) ) return i+1;return 0; //未查找到指定元素
} //find（5）取值（获取顺序表第pos个位置的元素）
public T get (int pos)
{ //返回第pos个元素，若pos<1或pos>this.length，返回nullif(pos<1||pos>this.length) {System.out.println(“pos值不合法”) ;return null; } //i值不合法，返回nullreturn this.listArray[pos-1];//将第pos个元素返回，其下标为pos-1
}
（6）修改第pos个位置的元素值
public boolean set( T obj， int pos)
{//将第pos个元素设置为obj，1<=pos<=this.lengthif(pos<1 || pos>this.length) //位序不合法return false;this. listArray[pos-1] = obj;return true;
}（7）求表长
public int size()
{ return this.length;
}
（8）判空
public boolean isEmpty()
{ return this.length==0;
}
（9）遍历
public void nextOrder()
{ for(int i=0;i<this.length; i++)System.out.print(this.listArray[i]+” ”); System.out.println();
}
(10) 清空表
public void clear()
{ this.length=0;
}
›主程序类
public class Test3{
public static void main(String[] args){
//创建一个能容纳5个元素的整型顺序表L
SequenceList<Integer> L=new SequenceList<Integer>(5);
int status,e,i;
int []a={23,56,12,49,35};
for(i=0;i<a.length;i++)
L.add(a[i], i+1); //将数组a中各个元素插入顺序表中
System.out.println("顺序表中的数据元素为:");
L.nextOrder();
L.add(30,4): //在第4个位置插入数据元素30
System.out.printn("执行插入操作后顺序表中的数据元素为:");
L.nextOrder();
e=L.remove(5); //删除第5个元素
System.out.println("执行删除操作后顺序表中的数据元素为:");
L.nextOrder();
i=L.find(12); //在顺序表L中查找元素12的位置
System.ou.println("元素 12 在顺序表中的位置为:"+i);
}
}线性表的链式表示和实现
线性表的链式表示
链式存储结构特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以连续，也可以不连续）。
单链表可 由头指针唯一确定，头指针 指向链表中第一个结点 。首元结点是存储第一个元素的结点。若要访问数据元素 ai ， 须从头指针出发， 顺着指针域逐个结点访问，直至第 i 个结点。因此，线性表的链式存储结构 只适合顺序访问，不支持直接访问。
线性链表也即单链表，含有一个指针域。
两种形式：
l 不带头结点 ：头指针指向首元结点l 带头结点 ：头指针指向头结点，头结点的地址域指示首元结点头结点：首元结点之前附设的一个结点，数据域内可什么都不存，头结点不计入链表长度
单链表的结点类定义
public class Node<T>{
T data; //数据域
Node<T> next; //指针域
public Node(T data){this(data, null);}
public Node(){ this(null, null);}
public Node(T data, Node<T> next)
{this.data = data; this.next = next;
}
public String toString()
{ return this.data.toString();}
}
单链表的实现
public class LinkList<T>{ //单链表类Node<T> head; //成员变量，头指针int length； //表长，可无该成员，后面的算法都针对无length的链表//单链表的初始化public LinkList() //不带头结点的单链表构造方法{ head = null; //创建空链表}public LinkList() //带头结点的单链表构造方法{head = new Node<T>(); //创建空链表}
注意：一个链表只能选一种形式，带头结点或不带头结点，以上两个构造方法只在程序中写一个即可。
链表算法练习
链表
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.valueOf(sc.nextLine().trim());for (int i = 0; i < n; i++) {String [] operator=sc.nextLine().split(" ");if ("insert".equals(operator[0])) {insert(Integer.valueOf(operator[1]), Integer.valueOf(operator[2]));} else {delete (Integer.valueOf(operator[1]));}}ListNode node = head;if (node.next == null) {System.out.println("NULL");return;}while (node.next != null) {System.out.print(node.next.val + " ");node = node.next;}}public static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public static ListNode head = new ListNode(-1);public static void insert(int x, int y) {ListNode newNode = new ListNode(y);ListNode node = head;int sign = 0;while (null != node.next) {if (node.next.val == x) {newNode.next = node.next;node.next = newNode;sign = 1;break;}node = node.next;}if (sign == 0) {node.next = newNode;}}public static void delete (int x) {ListNode node = head;while (null != node.next) {if (node.next.val == x) {node.next = node.next.next;break;}node = node.next;}}
}个人感觉这道题比较简单，涉及到一些链表的基本操作，查找、删除、添加等。但是值得注意的是关于数据的输入。 int n = Integer.valueOf(sc.nextLine().trim());
nextLine()方法读取输入中的一整行文本，包括所有字符，直到遇到换行符。然后，你可以使用trim()方法去除字符串两端的空白字符，并通过Integer.valueOf()或Integer.parseInt()尝试将其转换为整数。这种方法更适合处理用户可能输入的复杂文本数据。nextInt()方法更适用于需要用户输入单个整数的场景，并且你希望程序在读取到非整数时能够立即报错。nextLine()方法提供了更大的灵活性，因为它允许你读取一整行文本，然后可以根据需要对这部分文本进行各种处理，包括转换为整数、分割成多个部分、进行字符串操作等。- String [] operator=sc.nextLine().split(" ");字符串将在每个空格处被拆分。
- 拆分的结果是一个字符串数组，其中包含了被空格分隔的所有子字符串。
反转链表
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @return ListNode类*/public ListNode ReverseList (ListNode head) {ListNode pre = null;ListNode cur = head;while (cur != null) {//保存的是cur的下一个值ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}
head是头节点，首先创建了两个节点pre前驱节点和cur代表当前节点。让当前节点初始化为head头节点；pre初始化为null。因为当反转结束时，head节点会变成尾节点，而尾节点的指针指向null。循环判断的条件是当前节点为null，cur为最后一个节点时，遍历结束。先保存一下cur的下一个节点，避免反转指针之后找不到，让当前的前驱节点为cur的下一个节点，，再移动cur和pre。注意：先移动pre再移动cur