数组,在内存上给出了连续的空间.链表,内存地址上可以是不连续的,每个链表的节点包括原来的内存和下一个节点的信息(单向的一个,双向链表的话,会有两个). 数组优于链表的: 1.内存空间占用的少,因为链表节点会附加上一块或两块下一个节点的信息.但是数组在建立时就固定了.所以也有可能会因为建立的数组过大或不足引起内存上的问题. 2.数组内的数据可随机访问.但链表不具备随机访问性.这个很容易理解.数组在内存里是连续的空间.比如如果一个数组地址从100到200,且每个元素占用两个字节,那么100-200之间的任何一个偶数都是数组元素的地址.可以直接访问.链表在内存地址可能是分散的.所以必须通过上一节点中的信息找能找到下一个节点. 3.查找速度上.这个也是因为内存地址的连续性的问题.不罗索了. 链表优于数组的: 1.插入与删除的操作.如果数组的中间插入一个元素,那么这个元素后的所有元素的内存地址都要往后移动.删除的话同理.只有对数据的最后一个元素进行插入删除操作时,才比较快.链表只需要更改有必要更改的节点内的节点信息就够了.并不需要更改节点的内存地址. 2.内存地址的利用率方面.不管你内存里还有多少空间,如果没办法一次性给出数组所需的要空间,那就会提示内存不足,磁盘空间整理的原因之一在这里.而链表可以是分散的空间地址. 3.链表的扩展性比数组好.因为一个数组建立后所占用的空间大小就是固定的.如果满了就没法扩展.只能新建一个更大空间的数组.而链表不是固定的,可以很方便的扩展.
数组与链表的优缺点； 数组:
优点：使用方便 ，查询效率 比链表高，内存为一连续的区域
缺点：大小固定，不适合动态存储，不方便动态添加 链表：
优点：可动态添加删除 大小可变 缺点：只能通过顺次指针访问，查询效率低
补充：
顺序表的优点:查找方便,适合随机查找 顺序表的缺点:插入、删除操作不方便，因为插入、删除操作会导致大量元素的移动 链接表的优点:插入、删除操作方便，不会导致元素的移动，因为元素增减，只需要调整指针。 顺序表的缺点:查找方便，不适合随机查找
链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。 链表顾名思义，要把各个元素链接起来才算撒。 通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。 双链表的化每个元素即要保存到下一个元素的指针，还要保存一个上一个元素的指针。 循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。 数组是一组具有相同类型和名称的变量的集(百度)合。这些变量称为数组的元素,每个数组元素都有一个编号,这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。 数组在进行查找，排序操作是很方便；链表不需要连续空间，而且作插入操作方便！ 分配空间上也不同，建立过程也不同！
链表和数组的本质差异 1 在访问方式上 数组可以随机访问其中的元素 链表则必须是顺序访问，不能随机访问 2 空间的使用上 链表可以随意扩大 数组则不能
https://www.cnblogs.com/itdi/p/6590810.html
读懂了上面的下面我来实现一个简单的链表，对于初学者我希望你读懂下面的每一行代码，对你有好处。
public class Node<T> { private Node next; private T value; public Node(T value) { this.value = value; } public Node addNextNode(Node node) { this.next = node; return next; } public T getValue() { return value; } public boolean hasNext() { return this.next == null ? false : true; } public void addToTail(Node node) { Node temp = this; while (temp.hasNext()) { temp = next.addNextNode(node); } temp.next = node; } public Node getNext() { return next; } //获取尾节点的数据 public Node getNodeTail() { Node tmpnode = this; while (tmpnode.hasNext()) { tmpnode = tmpnode.getNext(); } return tmpnode; } //输出当前节点往下的所有节点的value字符串形式 @Override public String toString() { Node tmpnode=this; T tmpvalue=this.value; while (tmpnode.hasNext()){ tmpvalue= (T) (tmpvalue+" > "+tmpnode.next.getValue()); tmpnode=tmpnode.next; } return (String) tmpvalue; } //tmpnode.next.value这个就是找到的节点 public void deleteNode(Node header, Node denode){ Node tmpnode=header; while (tmpnode.hasNext()){ System.out.println("遍历"); if (tmpnode.next.equals(denode)){ // 删除找到的节点 tmpnode.next=tmpnode.next.next; } tmpnode=tmpnode.next; } } @Override public boolean equals(Object o) { // 第一句话是比较this与o是不是同一个对象 若是的话直接返回true if (this == o) return true; if (o == null || this.getClass() != o.getClass()) return false; Node<?> node = (Node<?>) o; if (next != null ? !next.equals(node.next) : node.next != null) return false; return value != null ? value.equals(node.value) : node.value == null; } @Override public int hashCode() { int result = next != null ? next.hashCode() : 0; result = 31 * result + (value != null ? value.hashCode() : 0); return result; } } public class Main { public static void main(String[] args) { //头节点 Node<Integer> head = new Node(10); //第一个节点 Node<String> firstNode = new Node("这是100"); //第二个节点 Node<Object> secondNode = new Node(1000); //在尾部插入第三个节点 head.addNextNode(firstNode).addNextNode(secondNode).addToTail(new Node<String>("尾部节点")); //输出最后一个节点的数据 System.out.println(secondNode.getNodeTail().getValue()); // 输出所有节点的数据 firstNode.deleteNode(head,secondNode); System.out.println(head.toString()); } }
