一:链表是什么
1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。
2、结点包括两个部分:(1)存储数据元素的数据域(内存空间),(2)存储指向下一个结点地址的指针域。
3、相对于线性表顺序结构,操作复杂。
4.、链表的分类
但是这里我们重点讲两种:单向不带头非循环链表、双向不带头非循环链表
二:链表的作用
1、实现数据元素的存储按一定顺序储存,允许在任意位置插入和删除结点。
2、包括单向结点,双向结点,循环结点
三:链表与数组的区别
说到链表那肯定要聊一下数组,为什么会出现链表呢?
(1)数组:使用一块连续的内存空间地址去存放数据,但
例如:
int a[5]={1,2,3,4,5}。突然我想继续加两个数据进去,但是已经定义好的数组不能往后加,只能通过定义新的数组
int b[7]={1,2,3,4,5,6,7}; ***********这样就相当不方便比较浪费内存资源,对数据的增删不好操作。
(2)链表:使用多个不连续的内存空间去存储数据, 可以 节省内存资源(只有需要存储数据时,才去划分新的空间),对数据的增删比较方便。
四:java中的链表-LinkedList
4.1 构造
LinkedList<E> list = new LinkedList<E>(); // 普通创建方法
//或者
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表
4.2 LinkList类的增加(add、addFirst、addLast)
// 引入 LinkedList 类
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] args) {
LinkedList<String> animals = new LinkedList<String>();
//普通添加
animals.add("cow");
animals.add("tiger");
animals.add("rabbit");
System.out.println("使用add添加动物后:"+animals);
// 使用 addFirst() 在头部添加元素
animals.addFirst("mouse");
System.out.println("使用addFirst添加动物后"+animals);
animals.addLast("dragon");
System.out.println("使用addLast添加动物后"+animals);
}
}
4.3 LinkedList类的查找(getFirst、getLast、迭代查询)
import java.util.LinkedList;
public class LinkedListTest {
public static void main(String[] args) {
LinkedList<String> animals = new LinkedList<String>();
//普通添加
animals.add("cow");
animals.add("tiger");
animals.add("rabbit");
System.out.println("使用add添加动物后:"+animals);
// 使用 addFirst() 在头部添加元素
animals.addFirst("mouse");
System.out.println("使用addFirst添加动物后"+animals);
animals.addLast("dragon");
System.out.println("使用addLast添加动物后"+animals);
animals.removeFirst();
//删除
System.out.println("使用removeFirst删除动物后"+animals);
animals.removeLast();
System.out.println("使用removeLast删除动物后"+animals);
//查找
System.out.println("使用getFirst获取到的动物是:"+animals.getFirst());
System.out.println("使用getLast获取到的动物是:"+animals.getLast());
}
}
4.4 api
4.5 对ArrayList和LinkedList的选择
以下情况使用 ArrayList :
频繁访问列表中的某一个元素。
只需要在列表末尾进行添加和删除元素操作。
以下情况使用 LinkedList :
你需要通过循环迭代来访问列表中的某些元素。
需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。
文章评论