[TOC]
结果展示
方块1; 黑桃1; 梅花3; 红桃4; 梅花4; 红桃5; 方块5; 梅花6; 方块7; 红桃8; 黑桃9; 梅花9; 红桃11; 梅花12; 红桃12; 梅花13; 红桃13;
梅花1; 红桃1; 梅花2; 黑桃4; 方块4; 黑桃5; 梅花5; 方块6; 红桃6; 梅花7; 黑桃8; 方块9; 红桃10; 方块10; 黑桃11; 梅花11; 方块11;
方块2; 红桃2; 黑桃2; 方块3; 黑桃3; 黑桃6; 黑桃7; 红桃7; 方块8; 梅花8; 红桃9; 黑桃10; 梅花10; 方块12; 黑桃12; 方块13; 黑桃13;
双链表实现
理解
- LinkedList就是双链表, 实现了List接口和Deque接口，Deque提供了双链表特性
- ArrayList 内部维护数组保存元素，所以他是连续线性表，而链表是不连续内存的线性表
- 双链表的每个元素是一个节点Node对象，每个节点保存前驱节点、后继节点的引用，单链表queue，每个节点保存后继节点的引用，例如MessageQueue
- 双链表本身持有第一个节点first，最后一个节点last，以及size属性
- 链表的插入操作，就是将插入元素装到一个新节点中，然后修改这个节点以及要插入位置前后两个节点的前驱后继引用，删除逆推
- 链表的查找操作，循环查找的索引次数，每次拿到后继节点，循环完就是了，双链表可以从两头选择开始
- 链式列表删除元素，时间复杂度O(1),而查找要从头或者尾开始，时间复杂度O(n)
- !!!但是链式列表元素装在节点中，所以删除时是先找到节点O(n)+删除节点O(1)
- 数组保存的元素，查找时用索引直接取，时间复杂度O(1),但是插入删除，需要将插入删除位置往后的元素都交换内存，时间复杂度O(n)
- 这种链表队列是双向的，先进先出；继承List有个子类是Stack栈，只有一个入口先进后出
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
这一点要看实际情况的。若只对单条数据插入或删除，ArrayList的速度反而优于LinkedList.但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList.因为ArrayList每插入一条数据，要移动插入点及之后的所有数据。
实现
- 1.根绝双链表的特性，先定义每个节点
private static class Node<E> {
E it;
Node<E> prev;
Node<E> next;
public Node(Node<E> prev, E it, Node<E> next) {
this.it = it;
this.prev = prev;
this.next = next;
}
}
- 2.定义头节点、尾节点、size
private int size;
private Node<E> first;
private Node<E> last;
- 3.插入操作
public void add(E it) {
Node<E> node = new Node<>(last, it, null);
if (last != null) {
last.next = node;
}
last = node;
if (first == null) {
first = node;
}
size++;
}
public void add(int index,E it){
//找到第index位置的节点，修改前驱后继引用
}
- 4.删除操作
- 删除元素时，找到删除的节点，修改前驱后继的引用
扑克发牌实现
- 定义Server类模拟服务端
- Server要实现生成牌，洗牌，发牌
/**
* 三带二服务器
*/
public class Server {
//所有的牌
private static List<Poker> list = new ArrayList<>();
//3个牌手的牌
private static LinkedList<LinkedList<Poker>> roles = new LinkedList<>();
static {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 13; j++) {
list.add(new Poker(i,j));
}
}
for (int i = 0; i < 54; i++) {
if(list.get(i).num == 3){
list.remove(i);
break;
}
}
for (int i = 0; i < 4; i++) {
roles.add(new LinkedList<Poker>());
}
}
/**
* 洗牌分牌
*/
public static void init(){
//随机取出发牌
int index = 0;
while (list.size() > 0){
int random = (int) (Math.random() * list.size());
Poker poker = list.remove(random);
roles.get(index).add(poker);
index++;
if(index >= 3){
index = 0;
}
}
}
/**
* 牌手拿牌 ：1 2 3
* @param index
*/
public static LinkedList<Poker> handOut(int index){
return roles.get(index - 1);
}
}
- 定义扑克对象Poker，包含花色和大小属性
public class Poker {
/**
* type = 红桃，方块，黑桃，梅花 = 1.2.3.4
* num = 1-13
*/
public int type,num;
public Poker(int type, int num){
this.type = type;
this.num = num;
}
@Override
public String toString() {
return name() + num + "; ";
}
public String name(){
switch (type){
case 1:
return "红桃";
case 2:
return "方块";
case 3:
return "黑桃";
case 4:
return "梅花";
}
return "";
}
}
- 客户端先调用洗牌，再拿牌,排序
Server.init();
LinkedList<Poker> list = Server.handOut(1);
sort(list);
System.out.println(list.toString());
public static void sort(LinkedList<Poker> list){
LinkedList<Poker>[] linkArr = new LinkedList[13];
for (int i = 0; i < 13; i++) {
linkArr[i] = new LinkedList<>();
}
for (int i = 0; i < list.size(); i++) {
Poker poker = list.get(i);
linkArr[poker.num - 1].add(poker);
}
list.clear();
for (LinkedList l:linkArr) {
list.addAll(l);
}
}
网友评论