每个元素有几个属性，存储值、存储上一个元素的引用(地址)、存储下一个元素的引用(地址)
linkedList是双向链表的数据结构
linkedList源码实现1.定义Node内部类
//定义一个节点类 （内部类）class Node{ private Node prev;//左节点，存储上一个元素的地址 private Node next;//右节点，存储下一个元素的地址 private Object data;//数据域，存储值 public Node(Node prev, Node next, Object data) { super(); this.prev = prev; this.next = next; this.data = data; }}
2、定义三个属性 ，第一个节点引用；最后一个节点的引用；长度
private Node first;private Node last;private int size;
3、实现size方法和get方法
public int size() { return size;}
方式一：
public Object get(int index) { if(index<0 || index>size-1) { throw new IndexOutOfBoundsException(); } //判断index 是靠前还是靠后 if(index < (size>>1)) { //右移一位相当于除二操作 //如果靠前 Node n = first; int count = 0; //从first开始遍历 循环中不循环first for(n = first;n.next!=null;n=n.next) { if(++count==index) { break; } } return n; }else { //如果靠后 Node n = last; int count = size-1; for(n = last;n.prev!=null;n=n.prev) { if(--count==index) { break; } } return n; }}
方式二：
public Object get(int index) { if(index<0 || index>size-1) { throw new IndexOutOfBoundsException(); } //判断index 是靠前还是靠后 if(index<(size>>1)) { Node n = first; for(int i = 0;i
计算机存储数据、组织数据的方式
1.数组：是线性结构的数据结构，存储的元素在空间上是连续的，遍历元素效率高
2.链表：分为单链表和双链表，插入和删除数据效率高
3.树：查找元素效率高
4.栈结构：存储的元素是 先进后出型的
5.队列：头只能添加元素，从尾获得元素（先进的元素是尾，后进的元素是头），是先进先出型
6.哈希：
三、linkedList的栈功能了解Stack类
import java.util.Stack;public class TestStack { public static void main(String[] args) { Stack stack = new Stack(); stack.push("a"); stack.push("b"); stack.push("c"); stack.push("d"); stack.push("e"); while(!stack.empty()) { //获取栈中的元素，先进后出 System.out.print(stack.pop()+" ");//e d c b a } }}
使用linkedList的栈功能
public static void main(String[] args) { linkedList list = new linkedList(); list.push("a"); list.push("b"); list.push("c"); list.push("d"); list.push("e"); while(list.size()!=0) { System.out.print(list.pop()+" ");// e d c b a } }
也可以二次封装为一个纯栈
public class MyStack { private linkedList list; public MyStack() { list = new linkedList(); } public void push(Object obj) { list.push(obj); } public Object pop() { return list.pop(); } public boolean isEmpty() { return list.size() == 0 ? true : false; }}
四、linkedList的队列功能import java.util.linkedList;public class TestlinkedList { public static void main(String[] args) { linkedList list = new linkedList(); list.offer("a"); list.offer("b"); list.offer("c"); list.offer("d"); list.offer("e"); while(list.size()!=0) { //先进先出 System.out.print(list.poll()+" ");//a b c d e } }}
ArrayList、linkedList、Vector的区别
ArrayList：是基于数组的集合，遍历时效率高，扩容是按50%
linkedList: 是基于双链表的集合，插入、删除时效率高
Vector：是线程安全的，效率低，扩容是按100%
五、CollectionsCollection和Collections一个是接口，一个是类
Collection是集合框架的父接口
Collections是为集合框架提供服务的工具类，所有的方法都是静态的，提供的功能方法：
折半查找法、集合的线程安全、拷贝、排序等
六、Comparable可排序的接口，一个类实现了该接口，要实现compareTo方法，描述比较的过程，一个类的对象有默认的比较规 则，要实现这个接口
public class Person implements Comparable{ private String sfz; private String name; private int age; public String getSfz() { return sfz; } public Person() { } public Person(String name, int age) { this.name = name; this.age = age; } public void setSfz(String sfz) { this.sfz = sfz; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public Person(String sfz, String name, int age) { super(); this.sfz = sfz; this.name = name; this.age = age; } @Override public boolean equals(Object obj) { if(this==obj) return true; if(obj instanceof Person) { Person p = (Person)obj; if(this.sfz.equals(p.sfz)) return true; } return false; } @Override public String toString() { return name; } @Override public int compareTo(Object o) { Person p = (Person)o; if(this.age>p.age) { return 1; } return -1; }}
七、Comparator（比较器）
比较器，一个类实现该接口，这个类就是一个比较器类了，将自定义的比较规则定义在比较器中
public class StringLengthComparator implements Comparator{ @Override public int compare(Object o1, Object o2) { String s1 = (String)o1; String s2 = (String)o2; if(s1.length()>s2.length()) return 1; return -1; }}
List list1 = new ArrayList();Collections.addAll(list1, "aadfss","cbdaaaf","acbc","acaad");Collections.sort(list1, new StringLengthComparator());System.out.println(list1);