一、线性表基础
1、线性表定义
线性表是最基本、最简单、也是最常用的一种数据结构。线性表是n个具有相同特性的数据元素的有限序列。
2、前驱、后驱元素
前驱元素 ：若A元素在B元素的前面，则称A为B的前驱元素
后继元素 ：若B元素在A元素的后面，则称B为A的后继元素
例如在上图中，A就是B的前驱元素，C就是B的后继元素。
3、线性表的特征
- 第一个数据元素没有前驱，这个数据元素被称为 头结点 ；
- 最后一个数据元素没有后继，这个数据元素被称为 尾结点 ；
- 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。
4、数学定义
如果把线性表用数学语言来定义，则可以表示为(a1,…ai-1,ai,ai+1,…an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素。
5、分类
按照存储方式可分为： 顺序存储 和 链式存储 。
顺序存储对应 顺序表 ，链式存储对应 链表 。
注：数组就是最常见的顺序表。
二、顺序表
1、顺序表的定义
//定义数据类型为泛型的顺序表
public class SequenceList<T>{
//定义顺序表，数组
private T[] elements;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
elements= (T[])new Object[capacity];
N=0;
}
}
在这里定义为泛型，是因为可以一劳永逸，可以接受任意类型的参数，定义为单个数据类型的话，就需要多个类。
注：以下各个方法都定义在SequenceList类中。
2、将顺序表置为空表
//清空顺序表，直接令 N = 0 即可
public void cls(){
N = 0;
}
将 N=0 ，实际上已经存储的数据并不会清空，只是在逻辑上来说是清空了，判断N是否为零来判断是否为空表。
3、判断顺序表是否为空表
//判断当前线性表是否为空表
public boolean isEmpty(){
return N == 0;
}
与 将顺序表置为空表 相对应理解。
4、获取线性表长度
//获取线性表的长度
public int length(){
return N;
}
5、获取指定位置的元素
//获取指定位置的元素
public T get(int i){
//如果i小于0或者大于当前元素个数，抛出异常
if (i<0 || i>=N){
throw new RuntimeException("当前元素不存在！");
}
return elements[i];
}
6、添加元素
//向线型表中添加元素t
public void insert(T t){
//如果表已满
if (N==elements.length){
throw new RuntimeException("当前表已满");
}
//在N处插入元素t并使N自增1，表示表中多了一个元素
//等同于 elments[N] = t; N++;
elements[N++] = t;
}
elements[N++] = t 需要理解一下。
7、在i元素处插入元素t
//在i元素处插入元素t
public void insert(int i,T t){
if (i==elements.length){
throw new RuntimeException("当前表已满");
}
if (i<0 || i>N){
throw new RuntimeException("插入的位置不合法");
}
//把i位置空出来，i位置及其后面的元素依次向后移动一位
for (int index=N;index>i;index--){
elements[index]=elements[index-1];
}
//把t放到i位置处
elements[i]=t;
//元素数量+1
N++;
}
添加元素和插入元素在链表中也有，需要重点掌握，注意观察插入方法的不同之处。
8、删除指定位置i处的元素，并返回该元素
public T remove(int i){
if (i<0 || i>N-1){
throw new RuntimeException("当前要删除的元素不存在");
}
//记录i位置处的元素
T result = elements[i];
//把i位置后面的元素都向前移动一位
for (int index=i;index<N-1;index++){
elements[index]=elements[index+1];
}
//当前元素数量-1
N--;
return result;
}
如果不需要返回值，可以不接收返回值，需要的时候再接收，不需要更改方法。
如：Object result = remove(2); 接收删除元素的值
remove(2); 不接收删除元素的值
9、查找元素t第一次出现的位置
//查找t元素第一次出现的位置
public int indexOf(T t){
if(t==null){
throw new RuntimeException("查找的元素不合法");
}
for (int i = 0; i < N; i++) {
if (elements[i].equals(t)){
return i;
}
}
return -1;
}
10、遍历表中所有元素
//打印当前线性表的元素
public void showEles(){
for (int i = 0; i < N; i++) {
System.out.print(elements[i]+" ");
}
}
11、测试类
/**
* Date: 2022/9/25 10:10
* Author: GuanBD
* Description:顺序表的测试类
*/
public class TestSequenceList {
public static void main(String[] args) {
SequenceList<String> squence = new SequenceList<>(5);
squence.insert(0, "张三");
squence.insert(1, "李四");
squence.insert(2, "王五");
squence.insert(3, "赵六");
squence.insert(4, "刘七");
int length = squence.length();
System.out.println("length："+length);
String string = squence.get(0);
System.out.println("0索引处元素："+string);
String remove = squence.remove(4);
System.out.println("删除掉的元素："+remove);
int index = squence.indexOf("王五");
System.out.println("王五第一次出现的位置"+index);
squence.showEles();
}
}
三、链表基础
1、链表概念
链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成。
2、链表分类
- 单向链表
- 单向循环链表
- 双向链表
- 双向循环链表
3、结点类的定义
public class Node<T> {
//存储元素
public T item;
//指向下一个结点
public Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
这只是一个参考模板，具体的实现会有所不同，不过都是通过这个类演变而来。
4、生成链表
public static void main(String[] args) throws Exception {
//构建结点
Node<Integer> first = new Node<Integer>(11, null);
Node<Integer> second = new Node<Integer>(13, null);
Node<Integer> third = new Node<Integer>(12, null);
Node<Integer> fourth = new Node<Integer>(8, null);
Node<Integer> fifth = new Node<Integer>(9, null);
//生成链表
first.next = second;
second.next = third;
third.next = fourth;
fourth.next = fifth;
}
四、单项链表
1、概念
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
2、定义
public class LinkList<T> {
//结点类
private class Node {
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
//记录头结点
private Node head;
//记录链表的长度
private int N;
public LinkList(){
//初始化头结点
head = new Node(null,null);
N=0;
}
}
注意这里节点类的定义。
注：以下方法都定义在LinkList类中。
3、清空链表
//清空链表
public void clear(){
head.next=null;
head.item=null;
N=0;
}
4、获取链表的长度
//获取链表的长度
public int length() {
return N;
}
4、判断链表是否为空
//判断链表是否为空
public boolean isEmpty() {
return N == 0;
}
5、获取指定位置i处的元素
//获取指定位置i处的元素
public T get(int i) {
if (i < 0 || i >= N) {
throw new RuntimeException("位置不合法！");
}
Node n = head.next;
for (int index = 0; index < i; index++) {
n = n.next;
}
return n.item;
}
6、添加元素
//向链表中添加元素t
public void insert(T t) {
//找到最后一个节点
Node n = head;
while (n.next != null) {
n = n.next;
}
Node newNode = new Node(t, null);
n.next = newNode;
//链表长度+1
N++;
}
7、向指定位置i处，添加元素t
//向指定位置i处，添加元素t
public void insert(int i, T t) {
if (i < 0 || i > N) {
throw new RuntimeException("位置不合法！");
}
//寻找位置i之前的结点
Node pre = head;
for (int index = 0; index <= i - 1; index++) {
pre = pre.next;
}
//位置i的结点
Node curr = pre.next;
//构建新的结点，让新结点指向位置i的结点
Node newNode = new Node(t, curr);
//让之前的结点指向新结点
pre.next = newNode;
//长度+1
N++;
}
8、删除指定位置i处的元素，并返回被删除的元素
//删除指定位置i处的元素，并返回被删除的元素
public T remove(int i){
if (i<0 || i>=N){
throw new RuntimeException("位置不合法");
}
//寻找i之前的元素
Node pre = head;
for (int index = 0; index <=i-1; index++) {
pre = pre.next;
}
//当前i位置的结点
Node curr = pre.next;
//前一个结点指向下一个结点，删除当前结点
pre.next = curr.next;
//长度-1
N--;
return curr.item;
}
9、查找元素t在链表中第一次出现的位置
//查找元素t在链表中第一次出现的位置
public int indexOf(T t){
Node n = head;
for (int i = 0;n.next!=null;i++){
n = n.next;
if (n.item.equals(t)){
return i;
}
}
return -1;
}
10、遍历表中所有元素
//打印当前线性表的元素
public void showEles(){
Node n = head;
while (n.next!=null){
n = n.next;
System.out.println(n.item);
}
}
11、测试类
public class TestLinkList {
public static void main(String[] args) throws Exception {
LinkList<String> list = new LinkList<>();
list.insert("张三");
list.insert(1, "李四");
list.insert(2, "王五");
list.insert(3, "赵六");
//测试length方法
System.out.println(list.length());
System.out.println("-------------------");
//测试get方法
System.out.println(list.get(2));
System.out.println("------------------------");
//测试remove方法
String remove = list.remove(1);
System.out.println(remove);
System.out.println(list.length());
System.out.println("----------------");
list.showEles();
}
}
五、双向链表
1、概念
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
2、定义
public class TwoWayLinkList<T> {
//记录头结点
Node head;
//记录尾结点
Node tail;
//表中元素个数
int N;
//初始哈链表
public TwoWayLinkList() {
head = new Node(null,null,null);
tail = null;
N = 0;
}
private class Node {
//记录当前节点的值
T item;
//前驱元素
Node pre;
//后驱元素
Node next;
public Node(T item, Node pre, Node next) {
this.item = item;
this.pre = pre;
this.next = next;
}
}
}
3、清空链表
//清空链表
public void clear() {
N = 0;
}
4、获取链表的长度
//获取链表的长度
public int getLength() {
return N;
}
5、判断链表是否为空
//判断链表是否为空
public Boolean isEmpty() {
return N == 0;
}
6、插入元素t(尾插法)
//插入元素t(尾插法)
public void insertToTail(T t) {
if (tail == null) {
tail = new Node(t, head, null);
head.next = tail;
} else {
Node oldLast = tail;
Node node = new Node(t, oldLast, null);
oldLast.next = node;
tail = node;
}
//长度+1
N++;
}
7、插入元素t(头插法)
//插入元素t(头插法)
public void insertToHead(T t) {
if (tail == null) {
tail = new Node(t, head, null);
head.next = tail;
} else {
//获取第一个结点
Node n = head.next;
//将创建的结点的前一个元素指向头结点，下一个元素指向原表中第一个结点
Node newNode = new Node(t, head, n);
//
head.next = newNode;
n.pre = newNode;
}
N++;
}
8、向指定位置i处插入元素t
//向指定位置i处插入元素t
public void insert(int i, T item) {
if (i < 0 || i > N) {
throw new RuntimeException("位置不合法！");
}
Node n = head;
for (int j = 0; j < i - 1; j++) {
n = n.next;
}
Node last = n.next;
Node newNode = new Node(item, n, last);
n.next = newNode;
last.pre = newNode;
}
9、获取指定位置i处的元素
//获取指定位置i处的元素
public T get(int i) {
if (i < 0 || i >= N) {
System.out.println("位置不合法！");
}
Node n = head;
for (int j = 0; j < i; j++) {
n = n.next;
}
return n.item;
}
10、找到元素t在链表中第一次出现的位置
//找到元素t在链表中第一次出现的位置
public int indexOf(T item) {
Node n = head;
for (int i = 0; i < N; i++) {
n = n.next;
if (item == n.item)
return i;
}
return -1;
}
11、删除位置i处的元素，并返回该元素
//删除位置i处的元素，并返回该元素
public T remove(int i) {
if (i < 0 || i > N) {
System.out.println("位置不合法！");
}
Node n = head;
for (int j = 0; j < i; j++) {
n = n.next;
}
Node curr = n.next;
Node curr_next = curr.next;
n.next = curr.next;
curr_next.pre = curr.pre;
N--;
return curr.item;
}
12、获取第一个元素
//获取第一个元素
public T getFirst(){
if (isEmpty()){
return null;
}
return head.next.item;
}
13、获取最后一个元素
//获取最后一个元素
public T getLast(){
if (isEmpty()){
return null;
}
return tail.item;
}
14、遍历表中所有元素
//遍历表中所有元素
public void showeles(){
if (isEmpty()){
System.out.println("链表为空");
}
Node n=head;
while(n.next!=null){
n=n.next;
System.out.println(n.item+" ");
}
}
15、测试类
package TowWayLinkList;
/**
* Date: 2022/9/25 23:06
* Author: GuanBD
* Description:
*/
public class TestTwoWay {
public static void main(String[] args) {
TwoWayLinkList<String> list = new TwoWayLinkList<>();
list.insertToHead("张三");
list.insertToTail("李四");
list.insert(2,"王五");
list.showeles();
System.out.println("------->");
int length = list.getLength();
System.out.println("链表长度："+length);
System.out.println("------->");
int index = list.indexOf("李四");
System.out.println("李四位置："+index);
System.out.println("------->");
list.clear();
list.showeles();
}
}
专栏：数据结构与算法
持续更新与改进中！！