线性表
线性表是一种最常用的，最简单，也是一种最基本的数据结构。线性表中有顺序存储和链式存储结构来表示，其中用顺序存储结构表示的线性表称为顺序表，用链式存储结构表示的线性表称为链表。链表又有单链表，双向链表，循环链表。
这里主要介绍单链表结构
链表是由结点来构成的，结点里面一个用来存放元素值的数据域和存放指针域
结点类:
package com.coderpwh.ch2;
/**
* 结点类
*/
public class Node {
// 结点值
public Object data;
// 后续结点的引用
public Node next;
public Node(){
}
public Node(Object data){
this(data,null);
}
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
线新表接口
package com.coderpwh.ch2;
/**
* 线性表接口
*/
public interface Ilist {
public void clear();
public boolean isEmpty();
public int length();
public Object get(int i);
public void insert(int i, Object x);
public void remove(int i);
public int indexOf(Object x);
public void display();
}
单链表里面的接口方法查询，遍历，增删。和jdk里面List基本上是一样的。除了List的扩容，基本上都覆盖到了！我们重点来看 insert 和 remove方法的实现。
单链表的增加，当然是带头结点的增加。
- 首先要查找到待插入位置的前驱结点
- 创建新的结点数据
- 修改相关结点指针域值从而使新节点插入到单链表中给定的位置。
/**
* 带头结点插入
*
* @param i
* @param x
* @throws Exception
*/
public void insert(int i, Object x) throws Exception {
Node p = head;
System.out.println("p的值:"+p);
int j = -1; // 带头结点插入
while (p != null && j <i-1) {
p = p.next;
++j;
}
if (p == null || j > i - 1) {
throw new Exception("插入的位置不合法!");
}
// 新节点
Node s = new Node(x);
s.next = p.next;
p.next = s;
}
不带头结点插入:
不带头结点的插入，表头插入时，新借点的指针要指向第一个结点，表头指向新节点如上图
表头插入：
s.next = head;
head = s;表中或表尾插入和带头结点插入是一样的
s.next = p.next;
p.next = s;
/*
* 不带头结点插入
*
*/
public void insert2(int i, Object x) throws Exception {
Node p = head;
int j = 0; // 此时无头结点
while (p != null && j < i - 1) {
p = p.next;
++j;
}
if (p == null || j > i) {
throw new Exception("插入位置不合理");
}
// 创建新结点
Node s = new Node(x);
if (i == 0) {
s.next = head;
head = s;
} else {
s.next = p.next;
p.next = s;
}
}
同样删除操作
- 先判断单链表是否为null，为null就结束操作，否就进行下一步操作
- 查找到待删除结点的前驱结点
- 修改链指针，使待删除结点从单链表中脱离出来
/**
* 删除操作
*
* @param i
* @throws Exception
*/
public void remove(int i) throws Exception {
Node p = head;
int j = -1;
// 此时是要找到第i个结点的前驱结点
while (p != null && j < i - 1) {
p = p.next;
++j;
}
if (p.next == null || j > i - 1) {
throw new Exception("删除的位置不合法!");
}
p.next = p.next.next;
}
完整的单链表实现:
package com.coderpwh.ch2;
/**
* 线性表类
*/
public class LinkList implements Ilist {
// 单链表的头指针
public Node head;
public LinkList() {
head = new Node();
}
public void clear() {
head.next = null;
head.data = null;
}
/**
* 判断头结点是否为空
*
* @return
*/
public boolean isEmpty() {
return head.next == null;
}
/**
* 单链表长度
*
* @return
*/
public int length() {
Node p = head.next;
int length = 0;
while (p != null) {
p = p.next;
++length;
}
return length;
}
public Object get(int i) throws Exception {
// 初始化首结点
Node p = head.next;
int j = 0;
while (p != null && j < i) {
// 指向后续结点
p = p.next;
++j;
}
if (p == null || j > i) {
throw new Exception("第" + i + "个元素不存在!");
}
return p.data;
}
/**
* 带头结点插入
*
* @param i
* @param x
* @throws Exception
*/
public void insert(int i, Object x) throws Exception {
Node p = head;
System.out.println("p的值:" + p);
int j = -1; // 带头结点插入
while (p != null && j < i - 1) {
p = p.next;
++j;
}
if (p == null || j > i - 1) {
throw new Exception("插入的位置不合法!");
}
// 新节点
Node s = new Node(x);
s.next = p.next;
p.next = s;
}
/**
* 不带头结点插入
*/
public void insert2(int i, Object x) throws Exception {
Node p = head;
int j = 0; // 此时无头结点
while (p != null && j < i - 1) {
p = p.next;
++j;
}
if (p == null || j > i) {
throw new Exception("插入位置不合理");
}
// 创建新结点
Node s = new Node(x);
if (i == 0) {
s.next = head;
head = s;
} else {
s.next = p.next;
p.next = s;
}
}
/**
* 删除操作
*
* @param i
* @throws Exception
*/
public void remove(int i) throws Exception {
Node p = head;
int j = -1;
// 此时是要找到第i个结点的前驱结点
while (p != null && j < i - 1) {
p = p.next;
++j;
}
if (p.next == null || j > i - 1) {
throw new Exception("删除的位置不合法!");
}
p.next = p.next.next;
}
/**
* 按值查找
*
* @param x
* @return
*/
public int indexOf(Object x) {
Node p = head.next;
int j = 0;
while (p != null && !p.data.equals(x)) {
p = p.next;
++j;
}
if (p != null) {
return j;
} else {
return -1;
}
}
/**
* 输出所有单链表中的所有结点
*/
public void display() {
Node node = head.next;
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
}
测试编写的LinkList的实现类
package com.coderpwh.ch2;
import java.util.Scanner;
public class TestLinkList {
public static void main(String[] args) throws Exception {
int n = 10;
LinkList L = new LinkList();
for (int i = 0; i < n; i++) {
L.insert(i, i);
}
System.out.println("请输入i的值:");
int i = new Scanner(System.in).nextInt();
if (0 < i && i <= n) {
System.out.println("第" + i + "个元素的直接前驱是:" + L.get(i - 1));
} else {
System.out.println("第" + i + "个元素的直接前驱不存在!");
}
}
}
以上都是对整个单链表的数据结构的复习，后面复习栈与队列。复习了单链表，那么问题来了 jdk里面的List是如何实现扩容的？
源码地址:
https://github.com/coder-PengWenHao/myblogs
