1.线性表的概念
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构,常见的线性表:顺序表、链表、栈、队列... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物 理上存储时,通常以数组和链式结构的形式存储。
2.顺序表
顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
2.1 顺序表实现
interface SeqListInterface<T> {
void add(T data);
void add(int pos, T data);
boolean contains(T toFind);
int indexOf(T toFind);
T get(int pos);
void set(int pos, T value);
void remove(T toRemove);
int size();
void clear();
void display();
}
class GenericSeqList<T> implements SeqListInterface<T> {
private T[] array;
private int size;
@SuppressWarnings("unchecked")
public GenericSeqList() {
array = (T[]) new Object[10];
}
@SuppressWarnings("unchecked")
public GenericSeqList(int initcapacity) {
array = (T[]) new Object[initcapacity];
}
public void add(T data) {
add(size, data);
}
public void add(int pos, T data) {
if (pos < 0 || pos > size) {
throw new IndexOutOfBoundsException("Invalid position for insertion.");
}
if (size == array.length) {
T[] newArray = (T[]) new Object[array.length * 2];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
}
for (int i = size; i > pos; i--) {
array[i] = array[i - 1];
}
array[pos] = data;
size++;
}
public boolean contains(T toFind) {
for (int i = 0; i < size; i++) {
if (array[i].equals(toFind)) {
return true;
}
}
return false;
}
public int indexOf(T toFind) {
for (int i = 0; i < size; i++) {
if (array[i].equals(toFind)) {
return i;
}
}
return -1;
}
public T get(int pos) {
if (pos < 0 || pos >= size) {
throw new IndexOutOfBoundsException("Invalid position for retrieval.");
}
return array[pos];
}
public void set(int pos, T value) {
if (pos < 0 || pos >= size) {
throw new IndexOutOfBoundsException("Invalid position for setting.");
}
array[pos] = value;
}
public void remove(T toRemove) {
int index = indexOf(toRemove);
if (index!= -1) {
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size--;
}
}
public int size() {
return size;
}
public void clear() {
size = 0;
}
public void display() {
for (int i = 0; i < size; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
GenericSeqList<Integer> seqList = new GenericSeqList<>();
seqList.add(5);
seqList.add(10);
seqList.add(15);
seqList.display();
seqList.add(1, 20);
seqList.display();
System.out.println(+ seqList.contains(10));
System.out.println("Index of 15: " + seqList.indexOf(15));
seqList.set(2, 25);
seqList.display();
seqList.remove(20);
seqList.display();
System.out.println("Size: " + seqList.size());
seqList.clear();
System.out.println("Size after clear: " + seqList.size());
}
}
2.2. ArrayList使用与构造
ArrayList() 无参构造 ArrayList(Collection<? extends E> c) 利用其他 Collection 构建 ArrayList ArrayList(int initialCapacity) 指定顺序表初始容量
方法:
尾插 e boolean add (E e) 将 e 插入到 index 位置 void add (int index, E element) 尾插 c 中的元素 boolean addAll (Collection<? extends E> c) 删除 index 位置元素 E remove (int index) 删除遇到的第一个 o boolean remove (Object o) 获取下标 index 位置元素 E get (int index) 将下标 index 位置元素设置为 element E set (int index, E element) 清空 void clear () 判断 o 是否在线性表中boolean contains (Object o) 返回第一个 o 所在下标int indexOf (Object o) 返回最后一个 o 的下标int lastIndexOf (Object o) 截取部分 listList<E> subList (int fromIndex, int toIndex)
import java.util.ArrayList;
import java.util.List;
public class Test_Demo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("Hello");
list.add("java");
list.add("hello");
list.add("world");
list.add("测试33");
System.out.println(list);//打印列表元素
System.out.println(list.size());// 获取list中有效元素个数
// 获取和设置index位置上的元素
System.out.println(list.get(1));
list.set(1, "JAVA");
System.out.println(list.get(1));
// 在list的index位置插入指定元素,index及后续的元素统一往后搬移一个位置
System.out.println(list);
list.add(1, "Java数据结构");
System.out.println(list);
// 删除指定元素,找到了就删除,该元素之后的元素统一往前搬移一个位置
list.remove("Java数据结构");
System.out.println(list);
// 删除list中index位置上的元素,注意index不要超过list中有效元素个数,否则会抛出下标越界异常
list.remove(list.size() - 1);
System.out.println(list);
// 检测list中是否包含指定元素,包含返回true,否则返回false
if(list.contains("测试33")){
list.add("TRUE");
}
// 查找指定元素第一次出现的位置:indexOf从前往后找,lastIndexOf从后往前找
list.add("JavaSE");
System.out.println(list);
System.out.println(list.indexOf("JavaSE"));
System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之间的元素构成一个新的SubList返回,但是和ArrayList共用一个elementData数组
List<String> ret = list.subList(0, 4);// 0 1 2 3
System.out.println(ret);
list.clear();
System.out.println(list.size());
}
}
// 运行结果
// [Hello, java, hello, world, 测试33]
// 5
// java
// JAVA
// [Hello, JAVA, hello, world, 测试33]
// [Hello, Java数据结构, JAVA, hello, world, 测试33]
// [Hello, JAVA, hello, world, 测试33]
// [Hello, JAVA, hello, world]
// [Hello, JAVA, hello, world, JavaSE]
// 4
// 4
// [Hello, JAVA, hello, world]
// 0
2.3 ArrayList的遍历
ArrayList 可以使用三方方式遍历: for 循环+下标、foreach 、使用迭代器
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下标+for遍历
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍历
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
//迭代器
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}
2.4 ArrayList的扩容机制
ArrayList 是一个动态类型的顺序表,即:在插入元素的过程中会自动扩容。以下是 ArrayList 源码中扩容方式 源码:Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10; // 默认容量
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 获取旧空间大小
int oldCapacity = elementData.length;
// 预计按照1.5倍方式扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用户需要扩容大小 超过 原空间1.5倍,按照用户所需大小扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE,重新计算容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0,抛出OutOfMemoryError异常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
1.检测是否真正需要扩容,如果是调用 grow 准备扩容 2. 预估需要库容的大小 2.1初步预估按照 1.5 倍大小扩容 2.2如果用户所需大小超过预估1.5倍大小,则按照用户所需大小扩容 真正扩容之前检测是否能扩容成功,防止太大导致扩容失败 3. 使用 copyOf 进行扩容洗扑克算法
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
class Card {
public int rank; // 牌面值
public String suit; // 花色
@Override
public String toString() {
return String.format("[%s%d]", suit, rank);
}
}
public class Test_Demo {
public static String[] SUITS = {"♠", "♥", "♣", "♦"};
private static List<Card> buyDeck() {
List<Card> deck = new ArrayList<>(52);
for (int i = 0; i < 4; i++) {
for (int j = 1; j <= 13; j++) {
String suit = SUITS[i];
int rank = j;
Card card = new Card();
card.rank = rank;
card.suit = suit;
deck.add(card);
}
}
return deck;
}
private static void swap(List<Card> deck, int i, int j) {
Card t = deck.get(i);
deck.set(i, deck.get(j));
deck.set(j, t);
}
private static List<Card> shuffle(List<Card> deck){
Random rand = new Random(System.currentTimeMillis());
for (int i = deck.size() - 1; i >0 ; i--) {
int e =rand.nextInt(i);
swap(deck, i, e);
}
return deck;
}
public static void main(String[] args) {
List<Card> deck = buyDeck();
System.out.println("刚买回来的牌:");
System.out.println(deck);
shuffle(deck);
System.out.println("洗过的牌:");
System.out.println(deck);
// 三个人,每个人轮流抓 5 张牌
//列表的每个元素是列表
List<List<Card>> hands = new ArrayList<>();
hands.add(new ArrayList<>());
hands.add(new ArrayList<>());
hands.add(new ArrayList<>());
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
hands.get(j).add(deck.remove(0));//deck.remove(0)返回0
}
}
System.out.println("剩余的牌:");
System.out.println(deck);
System.out.println("A 手中的牌:");
System.out.println(hands.get(0));
System.out.println("B 手中的牌:");
System.out.println(hands.get(1));
System.out.println("C 手中的牌:");
System.out.println(hands.get(2));
}
}
当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java中又引入了LinkedList,即链表结构。
3. 链表:
3.1 链表的概念及结构
链表是一种 物理存储结构上非连续 存储结构,数据元素的 逻辑顺序 是通过元素之间的次序依次链接起来的线性表
我们重点掌握两种 : 无头单向非循环链表 : 结构简单 ,一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ,如哈希桶、图的邻接表等等。这种结构在笔试面试 中也出现很多。 无头双向链表 :在 Java 的集合框架库中 LinkedList底层实现就是无头双向循环链表。
3.2 链表的实现
public class SingleLinkedList {
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public void createList() {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
this.head = node1;
}
//头插法
public void addFirst(int data) {
ListNode newNode = new ListNode(data);
newNode.next = this.head;
this.head = newNode;
}
//尾插法
public void addLast(int data) {
ListNode head1 = new ListNode(data); // 记录头节点
head1 = this.head;
ListNode newNode = new ListNode(data);
if (this.head == null) {
this.head = newNode;
return;
}
ListNode current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
this.head = head1;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("数组越界访问");
}
ListNode newNode = new ListNode(data);
if (index == 0) {
newNode.next = this.head;
this.head = newNode;
return;
}
ListNode current = this.head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode current = this.head;
while (current!= null) {
if (current.val == key) {
return true;
}
current = current.next;
}
return false;
}
public void remove(int key) {
if (this.head == null) {
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode current = this.head;
while (current.next!= null) {
if (current.next.val == key) {
current.next = current.next.next;
return;
}
current = current.next;
}
}
// 删除所有值为 key 的节点
public void removeAllKey(int key) {
while (this.head!= null && this.head.val == key) {
this.head = this.head.next;
}
if (this.head == null) {
return;
}
ListNode current = this.head;
while (current.next!= null) {
if (current.next.val == key) {
current.next = current.next.next;
} else {
current = current.next;
}
}
}
//得到单链表的长度
public int size() {
int count = 0;
ListNode current = this.head;
while (current != null) {
count++;
current = current.next;
}
return count;
}
public void clear() {
}
public void display() {
ListNode current = this.head;
while (current!= null) {
System.out.print(current.val);
System.out.print(" ");
current = current.next;
}
System.out.println();
}
}
public class Test233 {
public static void main(String[] args) {
SingleLinkedList list = new SingleLinkedList();
list.createList();
list.addFirst(233);
list.addLast(235);
list.addFirst(233);
list.addLast(235);
list.addFirst(233);
list.addLast(235);
list.display();
list.remove(233);
list.display();
}
}
3.3.LinkedList的模拟实现
// 2、无头双向链表实现
public class MyLinkedList {
static class LinkNode {
public LinkNode pre;
public int val;
public LinkNode next;
public LinkNode(int val) {
this.val = val;
}
}
public LinkNode head;
public LinkNode last;
public void create_LinkedList(){
head = new LinkNode(0);
last = head;
}
//头插法
public void addFirst(int data){
LinkNode newLink = new LinkNode(data);
if(head == null){
head = newLink;
last = newLink;
}
else{
newLink.next = head;
head.pre=newLink;
head=newLink;
}
}
//尾插法
public void addLast(int data){
LinkNode newLink = new LinkNode(data);
if(head == null){
head = newLink;
last = newLink;
}else{
last.next = newLink;
newLink.pre=last;
last=newLink;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
;
if (index < 0 || index > size()) {
throw new ArrayIndexOutOfBoundsException("数组索引超出范围");
}
if (index == 0) {
addFirst(data);
return;
}
if(index == size()) {
addLast(data);
return;
}
LinkNode newLink = new LinkNode(data);
LinkNode cur2 = searchIndex(index);
newLink.next = cur2;
cur2.pre.next = newLink;
newLink.pre = cur2.pre;
cur2.pre = newLink;
}
private LinkNode searchIndex(int index){
LinkNode cur = head;
int count = 0;
while(count != index){
cur = cur.next;
count++;
}
return cur;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
LinkNode cur = head;
while(cur!=null){
cur=cur.next;
if(cur.val==key)
return true;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
LinkNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur.val == head.val) {
head = head.next;
head.pre = null;
} else {
if (cur.val == last.val) {
last = last.pre;
last.next = null;
} else {
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
}
}
return;
} else {
cur = cur.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
LinkNode cur = head;
while (cur != null) {
if (cur.val == key) {
if (cur.val == head.val) {
head = head.next;
if(head!=null){
head.pre = null;
}else{
head = null;
}
} else {
if (cur.next == null) {
cur.pre.next = cur.next;
last = cur.pre;
} else {
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
}
}
}
cur = cur.next;
}
}
//得到单链表的长度
public int size(){
int length=0;
LinkNode cur = head;
while(cur!=null){
cur=cur.next;
length++;
}
return length;
}
public void display(){
LinkNode cur = head;
while(cur!=null){
System.out.print(cur.val+" ");
cur=cur.next;
}
System.out.println();
}
public void clear(){
LinkNode cur = head;
while(cur!=null){
LinkNode curN = head.next;
cur.next=null;
cur.pre=null;
cur=curN;
}
head=null;
last=null;
}
}
public class Test233 {
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addFirst(3);
list.addFirst(2);
list.addFirst(1);
list.addLast(4);
list.addLast(5);
list.addLast(6);
list.addLast(6);
list.addLast(6);
list.addIndex(2,4);
list.display();
list.removeAllKey(6);
list.display();
}
}
LinkedList 的底层使用了双向链表 LinkedList 没有实现 RandomAccess 接口,因此 LinkedList 不支持随机访问
LinkedList () 无参构造 public LinkedList(Collection<? extends E> c) 吧 使用其他集合容器中元素构造Listimport java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Test233 { public static void main(String[] args) { // 构造一个空的LinkedList List<Integer> list1 = new LinkedList<>(); List<String> list2 = new ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List<String> list3 = new LinkedList<>(list2); } }
3.4 LinkedList方法与遍历
与ArrayListL类似,遍历不在赘述与演示
boolean add(E e) 尾插 e void add(int index, E element) 将 e 插入到 index 位置 boolean addAll(Collection<? extends E> c) 尾插 c 中的元素 E remove(int index) 删除 index 位置元素 boolean remove(Object o) 删除遇到的第一个 o E get(int index) 获取下标 index 位置元素 E set(int index, E element) 将下标 index 位置元素设置为 element void clear() 清空 boolean contains(Object o) 判断 o 是否在线性表中 int indexOf(Object o) 返回第一个 o 所在下标 int lastIndexOf(Object o) 返回最后一个 o 的下标 List<E> subList(int fromIndex, int toIndex) 截取部分 list标签:head,Java,cur,int,list,next,链表,详解,public From: https://blog.csdn.net/2301_80873677/article/details/141853371