数组与链表
undefined
数组
什么是数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
面试问题：数组与链表主要区别 链表适合插入、删除，时间复杂度是O(1)，而数组支持随机访问，根据下表随机访问的时间复杂度为O(1)；
链表
什么是链表
数组需要连续的储存空间，而链表不需要连续的存储空间，它是通过指针将一组连续的内存块串联起来， 比如申请的是 100MB 大小的链表，不会有问题。这里把内存块称为节点，它不仅要储存数据，而且需要记录下一个节点的地址，把记录下一个节点地址称为后继指针next。
链表第一个节点称为头结点，最后一个节点称为尾节点，头结点用于记录链表的基地址，就可以遍历整个链表，而尾节点不是指向下一个节点，而是指向空地址NUll。
并且链表插入、删除时间复杂度为O(1)，而随机访问时间复杂度是O(n)。
循环链表与双向链表
- 循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址，表示这就是最后的结点了，但是循环链表的尾结点指针是指向链表的头结点；
- 双向链表：单向链表只有一个方向，结点只有一个后继指针
next指向后面的结点。而双向链表，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点； - 如果存储相同的数据，双向链表需要更多的存储空间，但它支持双向遍历，操作灵活；
- 虽然单链表删除时间复杂度为O(1)，但每次删除都需要遍历整个链表，所以时间复杂度为O(n),而双向链表已经保存前驱节点，所以遍历时间复杂度为O(1)。
Java中的LinkedHashMap就采用双向链表数据结构
数组与链表区别
- 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读；
- 数组的缺点是大小固定：一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致内存不足出现（out of memory）。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时；
- 链表本身没有大小的限制，并且支持动态扩容；
单链表操作
反转
方法一：递归反转法，在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始，逆向反转各个结点的指针域指向。
public class SimpleLinkList {
public static void main(String[] args) {
Node head = new Node(0);
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
head.setNext(node1);
node1.setNext(node2);
node2.setNext(node3);
// 打印反转前的链表,定义一个h保存head节点数据，否则打印代码执行完毕head就为空了,下面反转代码就无法执行
Node h = head;
while (null != h) {
System.out.print(h.getData() + " ");
h = h.getNext();
}
// 调用反转方法
head = Reverse1(head);
System.out.println("\n**************************");
// 打印反转后的结果
while (null != head) {
System.out.print(head.getData() + " ");
head = head.getNext();
}
}
/**
* 递归，在反转当前节点之前先反转后续节点
*/
public static Node Reverse1(Node head) {
// head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
if (head == null || head.getNext() == null) {
return head;// 若为空链或者当前结点在尾结点，则直接返回
}
Node reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()
head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
head.setNext(null);// 前一结点的指针域令为null;
return reHead;// 反转后新链表的头结点
}
}
class Node {
private int Data;// 数据域
private Node Next;// 指针域
public Node(int Data) {
this.Data = Data;
}
public int getData() {
return Data;
}
public void setData(int Data) {
this.Data = Data;
}
public Node getNext() {
return Next;
}
public void setNext(Node Next) {
this.Next = Next;
}
}方法二：
public static Node reverse(Node list) {
Node curr = list, pre = null;
while (curr != null) {
Node next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}检查是否有环
例如这样的链表：A->B->C->D->B->C->D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。 采取了快慢指针：
public static boolean checkCircle(Node list){
if(list==null) return false;
Node fastNode=list.next;
Node slowNode = list;
while(fastNode!=null&&fastNode.next!=null){
fastNode = fastNode.next.next;
slowNode = slowNode.next;
if(fastNode==slowNode) return true;
}
return false;
}求单链表中间节点
public static Node findMiddleNode(Node list){
if (list == null) return null;
//fast 节点存储着list
Node fast = list;
Node slow = list;
while (fast.next != null && fast.next.next != null) {
//fast节点存储着fast下下节点内存地址
fast = fast.next.next;
slow = slow.next;
}
return slow;
}有序单链表合并
public static Node mergeSortNode(Node la,Node lb){
if(la==null) return lb;
if(lb==null) return la;
Node pNode = la;
Node qNode = lb;
Node head;
if(pNode.data<qNode.data){
head = pNode;
pNode = pNode.next;
}else {
head = qNode;
qNode = qNode.next;
}
Node rNode= head;
while(pNode!=null&&qNode!=null){
if(pNode.data<qNode.data){
rNode.next = pNode;
pNode = pNode.next;
}else {
rNode.next = qNode;
qNode = qNode.next;
}
rNode = rNode.next;
}
if(pNode!=null){
rNode.next =pNode;
}else {
rNode.next = qNode;
}
return head;
}删除倒数第k个节点
public static Node deleteLastNode(Node list, int k){
Node fast = list;
int i=1;
while(fast!=null&&i<k){
fast = fast.next;
++i;
}
if(fast==null) return null;
Node slow = list;
Node preve = null;
while(fast.next!=null){
fast = fast.next;
preve = slow;
slow = slow.next;
}
if(preve==null){
list = list.next;
}else {
preve.next = preve.next.next;
}
return list;
}单链表插入与删除
/**
* 单链表插入与删除
* @author zhangtianzhu
*
*/
public class SingleListDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
SingleListDemo sDemo = new SingleListDemo();
Node head = null;
//新增结点，第一个新增需要返回头指针
head = sDemo.insertNode(1, head);
sDemo.insertNode(2, head);
sDemo.insertNode(3, head);
sDemo.printListNode(head);
System.out.println(sDemo.getNodeLength(head));
//删除索引为2的节点
if((head = sDemo.deleteNode(2, head))!=null){
sDemo.printListNode(head);
}
//删除头结点
if((head = sDemo.deleteNode(1, head))!=null){
sDemo.printListNode(head);
}
}
/**
* 插入节点
* @param data
* @param head
* @return
*/
public Node insertNode(int data,Node head){
Node node = new Node(data);
if(head==null){
head = node;
return head;
}
Node curNode = head;
//循环找到当前尾结点
while(curNode.next!=null){
curNode = curNode.next;
}
//尾结点指针指向新增结点
curNode.next = node;
return head;
}
/**
* 单链表长度
* @param head
* @return
*/
public int getNodeLength(Node head){
Node node = head;
int length = 0;
while(node!=null){
node = node.next;
length++;
}
return length;
}
/**
* 删除结点
* @param index
* @param head
* @return
*/
public Node deleteNode(int index,Node head){
if(index<1||index>getNodeLength(head)){
return null;
}
//删除头结点
if(index==1){
head = head.next;
return head;
}
//从头结点下一个结点遍历
Node curNode = head.next;
//记录当前循环上一个节点用于删除结点
Node preNode = head;
int i = 2;
while(curNode.next!=null){
if(i==index){
//删除结点,前一个结点指向当前删除的下一个结点
preNode.next = curNode.next;
}else {
preNode = curNode;
curNode = curNode.next;
}
i++;
}
return head;
}
public void printListNode(Node head){
Node curNode = head;
while(curNode!=null){
System.out.print(curNode.getData()+" ");
curNode = curNode.next;
}
System.out.println();
}
}
class Node{
int data;
Node next = null;
public Node(int data) {
// TODO Auto-generated constructor stub
this.data = data;
}
public int getData() {
return data;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年8月4日 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录