Java集合（4）——LinkedList

LinkedList

LinkedList特有的方法： 1、方法介绍： addFirst（E e）：把元素添加到集合的首位置上 addLast（E e）：把元素添加到集合的末尾处 getFirst（）：获取集合中首位置的元素 getLast（）：获取集合中末尾处的元素 removeFirst（）：删除集合中的首位置元素并返回 removeLast（）：删除集合中的末尾元素并返回 如果集合中没有元素，获取或者删除元素抛：NoSuchElementException

public class Demo1 { public static void main(String[] args){ LinkedList list = new LinkedList(); list.add("小三"); list.add("小四"); list.add("小五"); list.addFirst("小六"); list.addLast("小七"); System.out.println("集合的元素:"+list); System.out.println("获取集合中首位置的元素:"+list.getFirst()); System.out.println("获取集合中末尾处的元素:"+list.getLast()); System.out.println("删除集合中首位置的元素并返回:"+list.removeFirst()); System.out.println("删除集合中末尾处的元素并返回:"+list.removeLast()); System.out.println("集合的元素:"+list); } }

2、数据结构： 1、栈：先进后出 push（） pop（） 2、队列：先进先出 offer（） poll（） 3、返回逆序的迭代器对象 descendingIterator（）：返回逆序的迭代器对象

public class Demo2 { public static void main(String[] args){ LinkedList list = new LinkedList(); list.add("小一"); list.add("小二"); list.add("小三"); list.push("小狗");//将该元素插入到集合的开头 System.out.println("删除集合中的首元素并返回:"+list.pop()); list.offer("小胜"); System.out.println("删除集合中的首元素并返回:"+list.poll()); Iterator it = list.descendingIterator(); while(it.hasNext()){ System.out.println(it.next()+","); } System.out.println(); System.out.println("集合的元素:"+list); } }

练习1：使用LinkedList实现堆栈数据结构的存储方式和队列数据结构的存储方式。

class Stack{ LinkedList list; public Stack(){ list = new LinkedList(); } //压栈 public void add(Object obj){ list.push(obj); } //弹栈 public Object pop(){ Object obj = list.pop(); return obj; } //获取元素的个数 public int size(){ return list.size(); } } class Queue{ LinkedList list; public Queue(){ list = new LinkedList(); } //入队 public void add(Object obj){ list.offer(obj); } //出队 public Object remove(){ return list.poll(); } //获取元素个数 public int size(){ return list.size(); } } public class Demo3 { public static void main(String[] args){ Stack stack = new Stack(); stack.add("小三"); stack.add("小四"); stack.add("小五"); System.out.println("栈的元素个数:"+stack.size()); // System.out.println("集合元素:"+stack.pop()); //小五，后进先出 int size = stack.size(); for(int i=0; i<size; i++){//为什么只输出了小五小四，因为在循环弹栈的过程中，stack.size也在变化 System.out.print(stack.pop()+" "); } System.out.println(); Queue queue = new Queue(); queue.add("小六"); queue.add("小七"); queue.add("小八"); System.out.println("队列的元素个数:"+queue.size()); // System.out.println(queue.remove()); //小六 先进先出 int qsize = queue.size(); for(int i=0; i<size; i++){ System.out.print(queue.remove()+" "); } } }

练习2：使用LinkedList存储一副扑克牌并实现洗牌功能 LinkedList:增删快，查找慢

class Poker{ //扑克牌的牌数 public static final int SUM = 52; //扑克牌的花色 String color; //扑克牌的点数 String num; public Poker(String color, String num){ this.color = color; this.num = num; } public String toString(){ return "{花色:"+this.color+" 点数:"+this.num+"}"; } } public class Demo4 { //创建扑克牌 public static LinkedList createPeker(){ //创建LinkedList对象存储扑克牌 LinkedList list = new LinkedList(); //定义扑克牌的花色 String[] colors = {"红桃", "方块", "黑桃", "梅花"}; //定义扑克牌的点数 String[] nums = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"}; //将扑克牌加入到list中 for(int i=0; i<colors.length; i++){ for(int j=0; j<nums.length; j++){ list.add(new Poker(colors[i], nums[j])); } } return list; } //显示扑克牌 public static void showPoker(LinkedList list){ // Iterator it = list.iterator(); // while(it.hasNext()){ // Poker poker = (Poker)it.next(); // System.out.print(poker + " "); // } for(int i=0; i<list.size(); i++){ Poker poker = (Poker)list.get(i); System.out.print(poker + " "); if(i%13 == 12){ //每13个一换行，也可以((i+1)%13 == 0) System.out.println(); } } } //洗牌方式1：建立一个新集合，不断从旧集合随机取出一张扑克牌加入到新集合中，完成洗牌 public static LinkedList shufflePoker1(LinkedList list){ Random random = new Random(); int size = list.size(); LinkedList newList = new LinkedList(); for(int i=0; i<size; i++){ int pokerNum = random.nextInt(list.size()); newList.add(list.get(pokerNum)); list.remove(pokerNum); } return newList; } //洗牌方式2:随机获取两个索引值，然后交换索引值处的元素，交换多次之后完成洗牌 public static void shufflePoker2(LinkedList list){ Random random = new Random(); for(int i=0; i<100; i++){ int index1 = random.nextInt(list.size()); int index2 = random.nextInt(list.size()); Poker poker1 = (Poker)list.get(index1); Poker poker2 = (Poker)list.get(index2); list.set(index1, poker2); list.set(index2, poker1); } } public static void main(String[] args){ //1.创建扑克牌 LinkedList pokers = createPeker(); //2.显示扑克牌 showPoker(pokers); //3.方式1洗牌 //LinkedList shufflePoker = shufflePoker1(pokers); //System.out.println("洗牌之后的扑克牌:"); //showPoker(shufflePoker); //4.方式2洗牌 shufflePoker2(pokers); System.out.println("洗牌之后的扑克牌:"); showPoker(pokers); } }

练习3：根据人的年龄进行排序存储

class Person{ public int age; public String name; public Person(int age, String name){ this.age = age; this.name = name; } public String toString(){ return "[年龄:"+this.age+" 姓名:"+this.name+"]"; } } public class Demo5 { //排序1:直接排序(从小到大) public static LinkedList sortAge1(LinkedList list){ int len = list.size(); for(int i=0; i<len; i++){ for(int j=i+1; j<len; j++){ Person p1 = (Person)list.get(i); Person p2 = (Person)list.get(j); if(p1.age > p2.age){ //交换位置可以用集合中的set(int index, Object obj) list.set(i, p2); list.set(j, p1); } } } return list; } //排序2:冒泡排序(从大到小) public static LinkedList sortAge2(LinkedList list){ int len = list.size(); for(int i=0; i<len-1; i++){ //进行的轮数 for(int j=0; j<len-i-1; j++){ Person p1 = (Person)list.get(j); Person p2 = (Person)list.get((j+1)); if(p1.age < p2.age){ list.set(j, p2); list.set(j+1, p1); } } } return list; } //排序3:冒泡排序(优化版1) public static void bubbleSort(int[] array){ int len = array.length; for(int i=0; i<len-1; i++){ boolean isSorted = true; for(int j=0; j<len-i-1; j++){ int temp = 0; if(array[j]>array[j+1]){ temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; isSorted = false; } } if(isSorted){ //只要上一轮没有比较（也就是说上一轮isSort没有变成false，说明剩下的元素都已经有序了，可以直接break退出循环） break; } } } //排序4:冒泡排序(优化版2) public static void bubbleSort2(int[] array){ //无序数列的边界，每次比较只需要比到这里为止， int sortBorder = array.length - 1; //记录最后一次交换的位置 int lastExchangeIndex = 0; for(int i=0; i<array.length; i++){ boolean isSorted = true; for(int j=0; j<sortBorder; j++){ int temp = 0; if(array[j]>array[j+1]){ temp = array[j]; array[j+1] = array[j]; array[j] = temp; isSorted = false; //记录最后一次交换元素的位置 lastExchangeIndex = j; } } sortBorder = lastExchangeIndex; if(isSorted){ break; } } } public static void main(String[] args){ LinkedList list = new LinkedList(); list.add(new Person(24, "壮年")); list.add(new Person(18, "成年")); list.add(new Person(100, "老年")); list.add(new Person(38, "中年")); list.add(new Person(13, "少年")); // sortAge1(list); sortAge2(list); for(int i=0; i<list.size(); i++){ Person p = (Person)list.get(i); System.out.print(p+" "); } System.out.println(); } }