1.简介
· 误区
1. 认为学习数据结构和算法需要很扎实的数学和编程功底，学起来并不容易;
2. 数据结构和算法在平时开发过程中的应用并不多，而且都有现成的类库接口让我们调用，没必要花太多时间去研究。
· 疑问
1. 为什么数据结构和算法使用率这么低，这些大公司还必问呢？这是因为数据结构和算法真的很重要，而且他们的使用率并不低，所有的程序中都有数据结构和算法的身影，他们默默的为程序服务，只是你没重视他们罢了。
· 列举我们为什么要学好数据结构和算法原因
1. 提升代码性能，结省空间复杂度和时间复杂度;
2. 算法锻炼自己的逻辑思维;
3. 你会不自觉的考虑你写的代码处理的数据量级是多少，会考虑你的代码是否能处理大量数据的情况
4. 更好的理解应用软件和框架，很多知名软件和框架中都大量用了数据结构算法，比如mysql的索引用了b+树，redis的list底层用了跳跃表，理解这些数据结构能更好的帮助我们理解使用这些软件。
5. 掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。
6. 一流的程序员搞算法，二流的程序员搞架构，三流的程序员搞业务;
数据结构与算法的关系：
1. 程序 = 数据结构 + 算法
2. 数据结构是算法的基础。
3. 图书馆储藏书籍你肯定见过吧？为了方便查找，图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号，就是书籍这种“数据”的存储结构。那我们如何来查找一本书呢？有很多种办法，你当然可以一本一本地找，也可以先根据书籍类别的编号，是人文，还是科学、计算机，来定位书架，然后再依次查找。笼统地说，这些查找方法都是算法。
4. 数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。
线性结构与非线性结构：
· 线性结构：数组、队列、链表和栈。
1. 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。
2. 线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的。
3. 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素结点存放数据元素以及相邻元素的地址信息。
· 非线性结构：二维数组，多维数组，广义表，树，图。
2.单向链表
链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
特点：
1. 链表是以结点形式存储的，是链式存储。
2. 每个结点包含data区域和next区域。
3. 如上图各个结点并不是连续存储的。
4. 链表分带头结点链表和没有带头结点链表，根据实际的需求来确定。
3.代码案例
我们首先需要一个实体类，它对应的便是单链表中每个节点的数据信息。
package com.szh.unidirectional; /** * */ public class GoodsNode { public int id; public String name; public double price; public GoodsNode next; public GoodsNode(int id, String name, double price) { this.id = id; this.name = name; this.price = price; } @Override public String toString() { return "GoodsNode{" + "id=" + id + ", name='" + name + '\'' + ", price=" + price + '}'; } }
接下来，我们写一个具体对单链表进行CRUD的操作类。
package com.szh.unidirectional; /** * */ public class DLLinkedList { private GoodsNode node = new GoodsNode(0, "", 0.0); //在单向链表末尾插入节点 public void addLast(GoodsNode goodsNode) { GoodsNode temp = node; //辅助变量 while (true) { if (temp.next == null) { break; } temp = temp.next; } temp.next = goodsNode; } //在单向链表中间某个位置插入节点 public void addOrder(GoodsNode goodsNode) { GoodsNode temp = node; //辅助变量 boolean flag = false; //标记变量 while (true) { if (temp.next == null) { break; } if (temp.next.id > goodsNode.id) { break; } else if (temp.next.id == goodsNode.id) { flag = true; break; } temp = temp.next; } if (flag) { System.out.println("已经存在了该商品，不能添加重复元素"); } else { goodsNode.next = temp.next; temp.next = goodsNode; } } //修改单向链表的某个节点 public void updateNode(GoodsNode goodsNode) { //如果链表为空 if (node.next == null) { System.out.println("链表为空...."); return; } GoodsNode temp = node.next; //辅助变量 boolean flag = false; //标记变量 while (true) { if (temp == null) { break; } if (temp.id == goodsNode.id) { //找到了要修改的链表节点 flag = true; break; } temp = temp.next; } if (flag) { temp.name = goodsNode.name; temp.price = goodsNode.price; } else { System.out.println("在整个链表中未找到目标节点...."); } } //删除单向链表的某个节点 public void deleteNode(int id) { //如果链表为空 if (node.next == null) { System.out.println("链表为空...."); return; } GoodsNode temp = node; //辅助变量 boolean flag = false; //标记变量 while (true) { if (temp.next == null) { break; } if (temp.next.id == id) { flag = true; break; } temp = temp.next; } if (flag) { temp.next = temp.next.next; } else { System.out.println("未找到删除的结点...."); } } //遍历单向链表，查看每个节点元素 public void list() { //如果链表为空 if (node.next == null) { System.out.println("链表为空...."); return; } GoodsNode temp = node.next; //辅助变量 int index = 0; while (true) { if (temp == null) { break; } System.out.println("第 " + (++index) + " 个节点元素为：" + temp); temp = temp.next; } //System.out.println("此单向链表中共有 " + index + " 个节点元素。"); } //统计单向链表中节点的个数 public int getNodeNum() { //如果链表为空 if (node.next == null) { System.out.println("链表为空...."); return 0; } GoodsNode temp = node.next; int num = 0; while (temp != null) { num++; temp = temp.next; } return num; } }
最后是我们的主方法类，我们需要对上面写好的代码功能进行测试。
package com.szh.unidirectional; /** * 单向链表相关操作 */ public class LinkedTest { public static void main(String[] args) { DLLinkedList dlLinkedList = new DLLinkedList(); GoodsNode goodsNode1 = new GoodsNode(1, "西游记", 55.55); GoodsNode goodsNode2 = new GoodsNode(2, "水浒传", 66.66); GoodsNode goodsNode3 = new GoodsNode(3, "红楼梦", 88.88); GoodsNode goodsNode4 = new GoodsNode(4, "三国演义", 99.99); System.out.println("单向链表的插入操作："); dlLinkedList.addLast(goodsNode1); dlLinkedList.addLast(goodsNode3); dlLinkedList.addOrder(goodsNode4); dlLinkedList.addOrder(goodsNode2); dlLinkedList.list(); System.out.println("此单向链表中共有 " + dlLinkedList.getNodeNum() + " 个节点元素。"); System.out.println(); System.out.println("单向链表的修改操作："); dlLinkedList.updateNode(new GoodsNode(3, "Java编程思想", 11.11)); dlLinkedList.list(); System.out.println("此单向链表中共有 " + dlLinkedList.getNodeNum() + " 个节点元素。"); System.out.println(); System.out.println("单向链表的删除操作："); dlLinkedList.deleteNode(2); dlLinkedList.list(); System.out.println("此单向链表中共有 " + dlLinkedList.getNodeNum() + " 个节点元素。"); } }
4.单向链表的CRUD图解
在单向链表的末尾插入新的节点。
在单向链表的中间某个位置插入新的节点。
单向链表的修改操作。（比较简单）
单向链表的删除操作。
