数组：
数组静态分配内存，在内存中连续
存储0,10,20,30,40,的数组的示意图如下：
image
数组的优点:
1.使用方便,查询效率、
2.随机访问性强（通过下标进行快速定位）
数组的缺点:
1.插入和删除效率低（插入和删除需要移动数据）
2.可能浪费内存（因为是连续的，所以每次申请数组之前必须规定数组的大小，如果大小不合理，则可能会浪费内存）
3.内存空间要求高，必须有足够的连续内存空间。
4.数组大小固定，不能动态拓展
链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此
链表的优点:
1.链表实现数据元素储存的顺序储存,是连续的
2.大小没有固定，拓展很灵活
3.不需要初始化容量，可以任意加减元素
链表的缺点:
1.不能随机查找，必须从第一个开始遍历，查找效率低
2.因为含有大量的指针域，占用空间较大
image
image
单链表：
链表是动态分配内存在内存中不连续，单链表只有一个向下的指针，指向下一个节点，单链表的定位时间复杂度是O(n)，插入删除的时间复杂度是O(1)
image
image
双链表：
链表是动态分配内容在内存中不连续，单双链表一致，双链表有两个指针header,next ，header指向上一个节点，next指向下一个节点
image
image
public class DoubleLink<T> {
// 表头
private Head<T> head;
// 节点个数
private int Count;
// 双向链表"节点"对应的结构体
private class Head<T> {
public Head header;
public Head next;
public T value;
public Head(T value, Head header, Head next) {
this.value = value;
this.header =header;
this.next = next;
}
}
// 构造函数
public DoubleLink() {
// 创建"表头"。注意：表头没有存储数据！
head = new Head<T>(null, null, null);
head.header = head.next = head;
// 初始化"节点个数"为0
Count = 0;
}
// 返回节点数目
public int size() {
return Count;
}
// 返回链表是否为空
public boolean isEmpty() {
return Count==0;
}
// 获取第index位置的节点
private Head<T> getNode(int index) {
if (index<0 || index>=Count)
throw new IndexOutOfBoundsException();
// 正向查找
if (index <= Count/2) {
Head<T> node = head.next;
for (int i=0; i<index; i++)
node = node.next;
return node;
}
// 反向查找
Head<T> node = head.header;
int rindex = Count - index -1;
for (int j=0; j<rindex; j++)
node = node.header;
return node;
}
// 获取第index位置的节点的值
public T get(int index) {
return getNode(index).value;
}
// 获取第1个节点的值
public T getFirst() {
return getNode(0).value;
}
// 获取最后一个节点的值
public T getLast() {
return getNode(Count-1).value;
}
// 将节点插入到第index位置之前
public void insert(int index, T t) {
if (index==0) {
Head<T> node = new Head<T>(t, head, head.next);
head.next.header = node;
head.next = node;
Count++;
return ;
}
Head<T> inode = getNode(index);
Head<T> tnode = new Head<T>(t, inode.header, inode);
inode.header.next = tnode;
inode.next = tnode;
Count++;
return ;
}
// 将节点插入第一个节点处。
public void insertFirst(T t) {
insert(0, t);
}
// 将节点追加到链表的末尾
public void appendLast(T t) {
Head<T> node = new Head<T>(t, head.header, head);
head.header.next = node;
head.header = node;
Count++;
}
// 删除index位置的节点
public void del(int index) {
Head<T> inode = getNode(index);
inode.header.next = inode.next;
inode.next.header = inode.header;
inode = null;
Count--;
}
// 删除第一个节点
public void deleteFirst() {
del(0);
}
// 删除最后一个节点
public void deleteLast() {
del(Count-1);
}
}
public class DlinkTest {
// 双向链表操作int数据
private static void inttest() {
int[] arr = {0,10,20,30};
System.out.println("\n----inttest----");
// 创建双向链表
DoubleLink<Integer> dlink = new DoubleLink<Integer>();
dlink.insert(0,10); // 将 30 插入到第一个位置
dlink.appendLast(20); // 将 20 追加到链表末尾
dlink.insertFirst(30); // 将 40 插入到第一个位置
// 双向链表是否为空
System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
// 双向链表的大小
System.out.printf("size()=%d\n", dlink.size());
// 打印出全部的节点
for (int i=0; i<dlink.size(); i++)
System.out.println("dlink("+i+")="+ dlink.get(i));
}
private static void stringtest() {
String[] array = {"zero","ten","twenty", "thirty"};
System.out.println("\n----stringtest----");
// 创建双向链表
DoubleLink<String> dlink = new DoubleLink<String>();
dlink.insert(0, array[1]); // 将 array中第2个元素 插入到第一个位置
dlink.appendLast(array[0]); // 将 array中第1个元素 追加到链表末尾
dlink.insertFirst(array[2]); // 将 array中第3个元素 插入到第一个位置
// 双向链表是否为空
System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
// 双向链表的大小
System.out.printf("size()=%d\n", dlink.size());
// 打印出全部的节点
for (int i=0; i<dlink.size(); i++)
System.out.println("dlink("+i+")="+ dlink.get(i));
}
// 内部类
private static class Student {
private int id;
private String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "["+id+", "+name+"]";
}
}
private static Student[] students = new Student[]{
new Student(0, "xiaoming"),
new Student(10, "xiaohua"),
new Student(20, "xiaodan"),
new Student(30, "xiaohong"),
};
private static void objecttest() {
System.out.println("\n----objecttest----");
// 创建双向链表
DoubleLink<Student> dlink = new DoubleLink<Student>();
dlink.insert(0, students[1]); // 将 students中第2个元素 插入到第一个位置
dlink.appendLast(students[0]); // 将 students中第1个元素 追加到链表末尾
dlink.insertFirst(students[2]); // 将 students中第3个元素 插入到第一个位置
// 双向链表是否为空
System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
// 双向链表的大小
System.out.printf("size()=%d\n", dlink.size());
// 打印出全部的节点
for (int i=0; i<dlink.size(); i++) {
System.out.println("dlink("+i+")="+ dlink.get(i));
}
}
public static void main(String[] args) {
inttest(); // 演示向双向链表操作"int数据"。
stringtest(); // 演示向双向链表操作"字符串数据"。
objecttest(); // 演示向双向链表操作"对象"。
}
}
网友评论