点击上方蓝色“ 方志朋 ”，选择“设为星标”
回复“666”获取独家整理的学习资料！
作者：远航
cnblogs.com/yang-guang-zhang/p/13884023.html
一、单链表
1、在我们数据结构中，单链表非常重要。它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面 LinkedList、HashMap（数组加链表）等等的底层都是用链表实现的。
2、下面是单链表的几个特点：
数据元素在内存中存放的地址是不连续的：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。
添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next
（1），然后将第一个元素的next指向插入结点（2），
不用在挪动后面元素。
删除效率高：删除一个元素时，先找到删除位置，将前一个的next指向删除位置的next，不用在挪动后面元素。
查询效率低：查询的时候必须从头开始，依次遍历，而数组因为它的内存是连续的，可以直接通过索引查找。
3、下面通过代码来实现单链表结构：
`package com.tlinkedList;
/**
* User:zhang
* Date:2020/10/26
**/
public class TLinkedList<T> {
private Node head;//链表头部
private int size;//链表元素的个数
public TLinkedList(){
head=null;
size=0;
}
// 将结点作为内部类。也可以新建一个Node类，作为结点
class Node{
private Node next;//下一个结点
private T t;//结点的数据
public Node(T t){
this.t=t;
}
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
// 在链表头部添加一个结点
public void addFirst(T t){
Node node = new Node(t);
node.next=head;
head=node;
size++;
}
// 在链表中间添加一个结点
public void addMid(T t,int index){
Node node = new Node(t);
Node mid=head;
for (int i = 0; i < index - 1; i++) {
mid=mid.next;
}
node.next=mid.next;
mid.next=node;
size++;
}
// 在链表尾部添加一个结点
public void addLast(T t){
Node node = new Node(t);
Node last=head;
while (last.next!=null){
last=last.next;
}
last.next=node;
node.next=null;
size++;
}
// 删除链表的头结点
public void removeFirst(){
head=head.next;
size--;
}
// 删除链表的中间元素
public void removeMid(int index){
Node mid=head;
if (index==0){
removeFirst();
return;
}
int j=0;
Node qMid=head;
while (j<index){
qMid=mid;
mid=mid.next;
j++;
}
qMid.next=mid.next;
size--;
}
// 删除链表的尾结点
public void removeLast(){
Node mid=head;
Node qMid=head;
while (mid.next!=null){
qMid=mid;
mid=mid.next;
}
qMid.next= null;
size--;
}
// 获取链表指定下标的结点
public Node get(int index){
Node mid=head;
if (index==0){
return head;
}
int j=0;
while (j<index){
mid=mid.next;
j++;
}
return mid;
}
public static void main(String[] args) {
TLinkedList<String> linkedList = new TLinkedList<>();
linkedList.addFirst("hello1");
linkedList.addFirst("hello2");
linkedList.addFirst("hello3");
for (int i = 0; i < linkedList.size; i++) {
System.out.println(linkedList.get(i).getT());
}
// linkedList.removeLast();
// linkedList.removeFirst();
// linkedList.addLast("hello4");
linkedList.addMid("hello",2);
System.out.println("--------------");
for (int i = 0; i < linkedList.size; i++) {
System.out.println(linkedList.get(i).getT());
}
}
}
`
结果如下：
二、栈(Stack)
1、一提到栈我们脑海就会浮现四个字“先进后出”，没错，它就是栈的最大特点。
2、栈的应用场景也非常多，比如将字符串反转、jvm里面的栈区等等。
3、栈里面的主要操作有：
-
push（入栈）：将一个数据元素从尾部插入
-
pop（出栈）：将一个数据元素从尾部删除
-
peek（返回栈顶元素）：将栈顶元素的数据返回
相当于只有一个开口就是尾部，只能从尾进，从尾出。
4、下面通过链表结构实现栈结构：
`package com.tStack;
/**
* User:zhang
* Date:2020/10/26
**/
public class Test_Stack<T> {
private Node head;//栈的头结点
private int size;//栈的元素个数
class Node{
private Node next;//下一个结点
private T t;//结点的数据
public Node(T t){
this.t=t;
}
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
public Test_Stack() {
head=null;
size=0;
}
public static void main(String[] args) {
Test_Stack<String> TStack = new Test_Stack<>();
TStack.push("hello1");
TStack.push("hello2");
TStack.push("hello3");
for (int i = 0; i < 3; i++) {
System.out.println(TStack.pop());
}
}
// 入栈
public void push(T t){
Node node = new Node(t);
if (size==0){
node.next=head;
head=node;
size++;
return;
}
if (size==1){
head.next=node;
node.next=null;
size++;
return;
}
Node lastNode=head;
while (lastNode.next!=null){
lastNode=lastNode.next;
}
lastNode.next=node;
node.next=null;
size++;
}
// 出栈
public T pop(){
if (size==0){
System.out.println("栈内无值");
return null;
}
if (size==1){
T t = head.getT();
head=null;
size--;
return t;
}
Node lastNode=head;
Node qNode=head;
while (lastNode.next!=null){
qNode=lastNode;
lastNode=lastNode.next;
}
T t = lastNode.getT();
qNode.next=null;
size--;
return t;
}
// 获取栈里面元素的个数
public int getSize(){
return size;
}
// 返回栈顶元素
public T peek(){
if (size==0){
System.out.println("栈内无值");
return null;
}
if (size==1){
return head.getT();
}
Node lastNode=head;
while (lastNode.next!=null){
lastNode=lastNode.next;
}
return lastNode.getT();
}
}
`
结果：
三、队列(Queue)
1、队列的特点也用“先进先出”四个字来概括。就是先进去的元素先输出出来。
2、我们常见的消息队列就是队列结构实现的。
3、队列的常见操作如下：
-
put（入队）：将一个结点插入到尾部。
-
pop（出队）：将头结点的下一个结点作为头，然后将原来的头结点删除。
4、通过链表结构实现队列：
`package com.tQueue;
/**
* User:zhang
* Date:2020/10/26
**/
public class TQueue<T> {
private Node front;//头结点
private Node tail;//尾结点
private int size;//队列中元素的个数
class Node {
private Node next;//下一个结点
private T t;//结点的数据
public Node(T t) {
this.t = t;
}
public T getT() {
return t;
}
public void setT(T t) {
this.t = t;
}
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public TQueue() {
front = tail = null;
}
// 入队
public void put(T t) {
Node node = new Node(t);
if (size == 0) {
front = tail = node;
size++;
return;
}
Node lastNode = front;
while (lastNode.next != null) {
lastNode = lastNode.next;
}
lastNode.next = node;
tail = node;
size++;
}
// 出队
public T pop() {
if (size == 0) {
System.out.println("队列中无值");
return null;
}
T t = front.getT();
front=front.next;
size--;
return t;
}
public static void main(String[] args) {
TQueue<String> tQueue = new TQueue<>();
tQueue.put("Hello1");
tQueue.put("Hello2");
tQueue.put("Hello3");
for (int i = 0; i < 3; i++) {
System.out.println(tQueue.pop());
}
}
}
`
结果：
文章有不足之处，欢迎大家留言指正，谢谢大家啦！
1 热门内容： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 第 3 次读 Effective Java，这 58 个技巧最值！ 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 10大黑客专用的 Linux 操作系统，每个都很酷！ 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 Spring官方都推荐使用的@Transactional事务，为啥我不建议使用！ 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 Java生鲜电商平台-监控模块的设计与架构 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 最近面试BAT，整理一份面试资料《Java面试BAT通关手册》，覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式：点“在看”，关注公众号并回复 666 领取，更多内容陆续奉上。 105 106 107 108 109 110 111 112 113 114 115 116 明天见(｡･ω･｡)ﾉ♡ 117 118 119 120
本文分享自微信公众号 - 方志朋（walkingstory）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。