线性表(数组、链表、队列、栈)详细总结
|字数总计:2.9k|阅读时长:12分钟|阅读量:
线性表是一种十分基础且重要的数据结构,它主要包括以下内容:
接下来,我将对这四种数据结构做一个详细的总结,其中对链表实现了十几种常见的操作。希望对你有所帮助。
1.数组
数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
注意点:①.数组是一种线性表;②.连续的内存空间和相同类型的数据
由于第二个性质,数组支持 “随机访问”,根据下表随机访问的时间复杂度为O(1);但与此同时却使得在数组中删除,插入数据需要大量的数据搬移工作。
低效的“插入”和“删除”
插入操作
假如数组的长度为n,我们需要将一个数据插入到数组的第k个位置,我们需要将第k~n位元素都顺序地往后挪动一位。
最好情况时间复杂度为O(1),此时对应着在数组末尾插入元素;
最坏情况时间复杂度为O(n),此时对应着在数组开头插入元素;
平均情况时间复杂度为O(n),因为我们在每个位置插入元素的概率相同,故(1+2+3+……+n)/n=O(n);
但是根据我们的需求,有一个特定的场景。如果数组的数据是有序的,那么我们在插入时就一定要那么做;但是如果数组中存储的数据并没有任何规律,数组只是被当成一个存储数据的集合,我们可以有一个取巧的方法:
直接将第k个元素搬移到数组元素的最后,把新的数据直接放入第k个位置即可(是不是很简单啊),这时插入元素的复杂度为O(1)。
删除操作
和插入操作一样,为了保证内存的连续性,删除操作也需要搬移数据。
最好情况时间复杂度为O(1),此时对应着删除数组末尾的元素;
最坏情况时间复杂度为O(n),此时对应着删除数组开头的元素;
平均情况时间复杂度为O(n),因为我们删除每个位置的元素的概率相同,故(1+2+3+……+n)/n=O(n);
当然,在某些特殊情况下,我们并不一定非要进行复杂的删除操作。我们只是将需要删除的数据记录,并且假装它以经被删除了。直到数组没有更多空间存储数据时,我们再触发一次真正的删除操作即可。
这其实就和生活中的垃圾桶类似,垃圾并没有消失,只是被“标记”成了垃圾,而直到垃圾桶塞满时,才会清理垃圾桶。
警惕数组访问越界
在 C 语言中,只要不是访问受限的内存,所有的内存空间都是可以自由访问的。如果疏忽会造成严重的后果。当然,Java会自动检测。
2.链表
- 链表结点表示
- 打印单链表
- 单链表根据索引插入结点
- 获取单链表的长度
- 打印单链表的长度
- 单链表删除指定索引的结点
- 单链表实现元素查找,返回是否存在布尔值
- 单链表删除指定索引的后续节点
- 单链表反转
- 递归地进行单链表反转
- 检测链表中是否含有环
- 删除倒数第k个结点
- 求中间节点
- 有序链表合并
链表结点表示
1 2 3 4
| public class Node{ int data; Node Next; }
|
打印单链表
1 2 3 4 5 6 7
| public class Method { public static void PrintNode (Node list){ for(Node x=list;x!=null;x=x.Next) System.out.print(x.data+" "); System.out.println(); }
|
单链表根据索引插入结点
1 2 3 4 5 6 7 8 9 10 11
| public static Node insert(Node first,int index,Node a){ Node ret = new Node(); ret.Next=first; Node p=ret; while((index--)!=0) p=p.Next; a.Next=p.Next; p.Next=a; return ret.Next; }
|
获取单链表的长度
1 2 3 4 5 6 7
| public static int GetLength(Node first){ int n=0; for(Node x=first;x!=null;x=x.Next){ ++n; } return n; }
|
打印单链表的长度
1 2 3
| public static void PrintLength(Node first){ System.out.println("Length : "+GetLength(first)); }
|
单链表删除指定索引的结点
1 2 3 4 5 6 7 8 9 10 11 12
| public static Node Delete(Node first,int index){ if(index<0||index>=GetLength(first)) return first; else{ Node ret=new Node(); ret.Next=first; Node p=ret; while((index--)!=0) p=p.Next; p.Next=p.Next.Next; return ret.Next; } }
|
单链表实现元素查找,返回是否存在布尔值
1 2 3 4 5 6
| public static boolean Find(Node first,int key){ for(Node x=first;x!=null;x=x.Next){ if(x.data==key) return true; } return false; }
|
单链表删除指定索引的后续节点
1 2 3 4 5 6 7 8
| public static void RemoveAfter(Node first,int index){ Node ret=new Node(); ret.Next=first; Node p=ret; while((index--)!=0) p=p.Next; p.Next.Next=null;
}
|
单链表反转
1 2 3 4 5 6 7 8 9 10
| 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; }
|
递归地进行单链表反转
1 2 3 4 5 6 7
| public static Node reverseRecursively(Node head){ if(head==null||head.Next==null) return head; Node reversedListHead=reverseRecursively(head.Next); head.Next.Next=head; head.Next=null; return reversedListHead; }
|
检测链表中是否含有环
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| public static boolean checkCircle(Node list){ if(list==null) return false;
Node fast=list.Next; Node slow=list;
while(fast!=null&&fast.Next!=null){ fast=fast.Next.Next; slow=slow.Next;
if(slow==fast) return true; } return false; }
|
删除倒数第k个结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| public static Node deleteLastKth(Node list,int k){ Node fast=list; int i=1; while(fast!=null&&i<k){ fast=fast.Next; ++i; }
if(fast==null) return list;
Node slow=list; Node prev=null; while(fast.Next!=null){ fast=fast.Next; prev=slow; slow=slow.Next; }
if(prev==null){ list=list.Next; }else{ prev.Next=prev.Next.Next; } return list; }
|
求中间节点
1 2 3 4 5 6 7 8 9 10 11 12 13
| public static Node findMiddleNode(Node list){ if(list==null) return null;
Node fast=list; Node slow=list;
while(fast!=null&&fast.Next!=null){ fast=fast.Next.Next; slow=slow.Next; }
return slow; }
|
有序链表合并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public static Node mergeTwoLists(Node l1,Node l2){ Node soldier=new Node(); Node p=soldier;
while(l1!=null&&l2!=null){ if(l1.data<l2.data){ p.Next=l1; l1=l2.Next; } else{ p.Next=l2; l2=l2.Next; } p=p.Next; }
if(l1!=null){ p.Next=l1;} if(l2!=null){ p.Next=l2;} return soldier.Next; }
|
3.栈
1.基于数组实现的顺序栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| package Stack;
public class ArrayStack { private int[] items; private int count; private int n; public ArrayStack(int n){ this.items=new int[n]; this.n=n; this.count=0; }
public boolean push(int item){ if(count==n) return false; items[count]=item; ++count; return true; }
public int pop(){ if(count==0) return -1; int tmp=items[count-1]; --count; return tmp; } public void PrintStack(){ for(int i=count-1;i>=0;--i){ System.out.print(items[i]+" "); } System.out.println(); } }
|
2.基于链表的链式栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| package Stack;
public class LinkedListStack { private Node top; private int N; private class Node{ int data; Node Next; } public boolean isEmpty(){ return top==null; } public int size(){ return N; }
public void push(int data){
Node newNode=top; top=new Node(); top.data=data; top.Next=newNode; ++N; } public int pop(){ if(top==null) return -1; int data=top.data; top=top.Next; N--; return data; } public void PrintStack(){ for(Node x=top;x!=null;x=x.Next){ System.out.print(x.data+" "); } System.out.println(); }
}
|
4.普通队列
- 基于数组实现的普通队列
- 基于链表实现的队列
- 基于数组实现的循环队列
1.基于数组实现的普通队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| package Queue;
public class ArrayQueue { private int[] items; private int n=0; private int head=0; private int tail=0;
public ArrayQueue(int capacity){ items=new int[capacity]; n=capacity; }
public boolean enqueue(int item){ if(tail==n) return false; items[tail]=item; ++tail; return true; }
public boolean enqueue1(int item){ if(tail==n){ if(head==0) return false; for(int i=head;i<tail;++i){ items[i-head]=items[i]; } tail=tail-head; head=0; } items[tail]=item; ++tail; return true; }
public int dequeue(){ if(head==tail) return -1; int ret=items[head]; ++head; return ret; }
public void PrintQueue(){ for(int i=head;i<tail;++i){ System.out.print(items[i]+" "); } System.out.println(); }
}
|
2.基于链表实现的队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| package Queue;
public class LinkedListQueue {
private Node head; private Node tail; private int N; private class Node{ int data; Node Next; } public boolean isEmpty(){ return head==null; } public int size(){ return N;}
public void enqueue(int data){ Node newNode=tail; tail=new Node(); tail.data=data; tail.Next=null; if(isEmpty()) head=tail; else newNode.Next=tail; ++N; } public int dequeue(){ int data=head.data; head=head.Next; if(isEmpty()) tail=null; N--; return data; }
public void PrintQueue(){ for(Node x=head;x!=null;x=x.Next){ System.out.print(x.data+" "); } System.out.println(); } }
|
3.基于数组实现的循环队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| package Queue;
public class CircularQueue { private int[] items; private int n=0; private int head=0; private int tail=0;
public CircularQueue(int capacity){ items = new int[capacity]; n=capacity; }
public boolean enqueue(int item){ if((tail+1)%n==head) return false; items[tail]=item; tail=(tail+1)%n; return true; }
public int dequeue(){ if(head==tail) return -1; int ret=items[head]; head=(head+1)%n; return ret; }
public void PrintQueue(){ if(n==0) return; for(int i=head;i%n!=tail;i=(i+1)%n){ System.out.print(items[i]+" "); } System.out.println(); } }
|
全文完