数据结构与算法(四)链表
1.链表
链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只管的表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的节点(链表中的每一个元素称为节点)组成,节点可以在运行时动态生成。
2.链表的特点
- 获取数据麻烦,需要遍历查找,比数组慢
- 方便插入、删除
3.链表的操作
-
第一张图:表示链表,可以看出链表的特点是一种在物理存储单元上非连续、非顺序的存储结构
-
第二张图:表示链表插入数据的过程,链表插入数据很简单,不需要像数组那样需要把要插入的位置后面的数据全部往后移动,只需要两步
- 让要插入的节点指向前一个节点指向的地址22 ->13
- 让前一个节点指向要插入的节点11 ->22
-
第三张图:表示链表的删除数据,链表的删除数据同理比顺序表(数组)简单,只需要让要删除节点的前一个节点指向删除节点指向的节点 11 ->12
4.单向链表
单向链表的节点包含两部分,第一个是数据域,第二个是指针域(指向下一个节点),其中头节点不存储数据,它的作用是用来找到这条链表
4.1实现思路
- 首先我们需要设计一个节点类作为单向链表类的内部类(代码实现的时候要记得是内部类),因为链表中的每一个元素称为节点。
类名 | Node |
---|---|
构造方法 | Node(T t,Node next) |
成员变量 | T data:存储数据 Node next:指向下一个节点 |
- 接下来就是设计我们的单向链表了
类名 | SingleLinkedList |
---|---|
构造方法 | SingleLinkedList() |
成员变量 | private Node head:记录首节点 private int length : 记录链表长度 |
成员方法 | 1. public void clear():清空单向链表 2. public boolean isEmpty() :判断链表是否为空,是返回true,否返回false 3. public int length():获取链表中元素的个数 4. public T get(int i ):读取并返回链表中的第i个元素的值 5. public int indexOf(T t):返回链表中首次出现的指定的数据元素的位序号 6. public void insert(T t):在链表中添加一个元素 7. public void insert(int i,T t):在链表的第i个元素之前插入一个值为t的数据元素 8. public T remove(int i ):删除并返回链表中第i个数据元素 9. public void showList():显示链表所有节点的数据 |
内部类 | private class Node |
4.2实现代码
//2.单向链表
public class SingleLinkedList<T>{
//记录首节点
private Node head;
//记录链表长度
private int length;
//构造器
public SingleLinkedList(){
//初始化头节点
this.head = new Node(null,null);
//初始化元素个数
this.length = length();
}
//清空单向链表
public void clear(){
head.next = null;
this.length = 0;
}
//判断链表是否为空,是返回true,否返回false
public boolean isEmpty(){
return length == 0;
}
//获取链表中元素的个数
public int length(){return length;}
//读取并返回链表中的第i个元素的值
public T get(int i ){
//通过循环,从头节点开始往后找,依次找i次,就可以找到对应d元素
Node temp = head.next;
for(int index = 0;index<i;index++){
temp = temp.next;
}
return temp.data;
}
//返回链表中首次出现的指定的数据元素的位序号
public int indexOf(T t){
//1.从头节点开始依次遍历每一个节点,取出data和t比较,如果相同就找到了
Node temp = head;
for(int i=0;temp.next!=null;i++){
temp = temp.next;
if(temp.data.equals(t)){
return i;
}
}
return -1;
}
//在链表中添加一个元素
public void insert(T t){
//1.找到当前最后一个节点
Node temp =head;
while (true){
if(temp.next == null){
//找到链表的最后
break;
}
//没有找到最后,将temp后移
temp = temp.next;
}
//2.创建新节点,保存元素t
Node newNode = new Node(t, null);
//3.让让最后一个节点指向新节点
temp.next = newNode;
//元素个数加1
length++;
}
//在链表的第i个元素之前插入一个值为t的数据元素
public void insert(int i,T t){
//1.找到i 位置的前一个节点
Node temp1 = head;
for(int index = 0;index <i-1; index++){
temp1 = temp1.next;
}
//2.找到i位置的后一个节点
Node nextNode = temp1.next;
//3.创建新节点,并指向 i位置的后一个节点
Node newNode = new Node(t,nextNode);
//4.i 位置的前一个节点指向新节点
temp1.next = newNode;
//5.元素个数加1
length++;
}
//删除并返回链表中第i个数据元素
public T remove(int i ){
//1.找到i位置的前一个节点
Node temp = head;
for(int index = 0;index<i;index++){
temp = temp.next;
}
//2.找到i位置的节点
Node currNode = temp.next;
//3.找到i位置的后一个节点
Node nextNode = currNode.next;
//4.i位置的前一个节点指向i位置的后一个节点
temp.next = nextNode;
//5.元素个数减1
length--;
return currNode.data;
}
//显示链表
public void showList(){
//判断链表是否为空
if(head.next == null){
System.out.println("链表为空");
return;
}
//因为头节点不能动,用temp用来辅助遍历
Node temp = head;
while (temp.next!=null){
temp = temp.next;
System.out.println("\t"+temp.data);
}
}
//1.节点类
class Node{
//储存数据
T data;
//指向下一个几点
Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
//重写toString()方法
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
}
4.3测试代码及效果
public class Test {
public static void main(String[] args) {
//创建单向链表
SingleLinkedList<String> linkedList = new SingleLinkedList<>();
//测试数据插入
linkedList.insert("孙悟空");
linkedList.insert("猪八戒");
linkedList.insert("沙僧");
linkedList.insert("唐僧");
//测试是否为空
System.out.println("是否为空:"+linkedList.isEmpty());
//测试获取个数
System.out.println("链表元素个数:"+linkedList.length());
//测试获取
System.out.println("获取到的元素:"+linkedList.get(1));
//测试指定数据首次出现位置
System.out.println("第一次出现位置:"+linkedList.indexOf("孙悟空"));
//测试指定位置插入插入元素
linkedList.insert(1,"白龙马");
//测试遍历
System.out.println("遍历结果:");
linkedList.showList();
//测试删除
System.out.println("成功删除:"+linkedList.remove(1));
}
}
5.双向链表
双向链表也叫双向表,是链表的一种,它由多个节点组成,每个节点都由一个数据域,和两个指针域组成,数据域用来存储数据,其中一个指针域用来指向其后继节点,另一个指针域用来指向前驱节点。链表的头节点的数据域不存数据,指向前驱节点的指针域的值为null,指向后继节点的指针域指向第一个真正存储数据的节点。
5.1实现思路
- 首先我们一样需要设计一个节点类,这个类的成员变量中比单向链表的节点类多了一个变量,用来指向上一个节点
类名 | Node |
---|---|
构造方法 | Node(T t,Node pre,Node next) |
成员变量 | T data:存储数据 Node next:指向下一个节点 Node pre:指向上一个节点 |
- 接下来就是设计我们的双向链表了,成员变量中多了一个指向尾节点的变量,成员方法多了两个分别是获取第一个元素和获取最后一个元素
类名 | DoubleLinkedList |
---|---|
构造方法 | DoubleLinkedList() |
成员变量 | private Node first:记录首节点 private Node last:记录尾节点 private int length:记录链表长度 |
成员方法 | 1. public void clear():清空双向链表 2. public boolean isEmpty() :判断链表是否为空,是返回true,否返回false 3. public int length():获取链表中元素的个数 4. public T get(int i ):读取并返回链表中的第i个元素的值 5. public int indexOf(T t):返回链表中首次出现的指定的数据元素的位序号 6. public void insert(T t):在链表中添加一个元素 7. public void insert(int i,T t):在链表的第i个元素之前插入一个值为t的数据元素 8. public T remove(int i ):删除并返回链表中第i个数据元素 9. public void showList():显示链表所有节点的数据 10. public T getFirst():获取第一个元素 11. public T getLast() :获取最后一个元素 |
内部类 | private class Node |
5.2实现代码
package com.lzf.linkedlist2;
import java.util.Iterator;
//2.双向链表
public class DoubleLinkedList<T> implements Iterable<T>{
//首节点
private Node head;
//最后一个节点
private Node last;
//链表长度
private int length;
//构造器
public DoubleLinkedList(){
//初始化头节点和尾节点
this.head = new Node(null,null,null);
this.last = null;
//初始化元素个数
this.length = 0;
}
//清空单向链表
public void clear(){
this.head.next = null;
this.last = null;
this.length = 0;
}
//判断链表是否为空,是返回true,否返回false
public boolean isEmpty(){
return length == 0;
}
//获取链表中元素的个数
public int length(){return length;}
//读取并返回链表中的第i个元素的值
public T get(int i ){
//通过循环,从头节点开始往后找,依次找i次,就可以找到对应的元素
Node temp = head.next;
for(int index = 0;index<i;index++){
temp = temp.next;
}
return temp.data;
}
//返回链表中首次出现的指定的数据元素的位序号
public int indexOf(T t){
//1.从头节点开始依次遍历每一个节点,取出data和t比较,如果相同就找到了
Node temp = head;
for(int i=0;temp.next!=null;i++){
temp = temp.next;
if(temp.data.equals(t)){
return i;
}
}
return -1;
}
//在链表中添加一个元素
public void insert(T t){
if(isEmpty()){
//如果链表为空
//1.创建新的节点
Node newNode = new Node(t, head, null);
//2.让新节点成为尾节点
last = newNode;
//3.让头节点指向尾节点
head.next = last;
}else {
//如果链表不为空
//1.创建新的节点
Node newNode = new Node(t,last,null);
//2.让当前尾节点指向新节点
last.next = newNode;
//3.让新节点成为尾节点
last = newNode;
}
//元素个数加1
length++;
}
//在链表的第i个元素之前插入一个值为t的数据元素
public void insert(int i,T t){
//1.找到i位置的前一个节点
Node temp = head;
for(int index=0;i<i;index++){
temp = temp.next;
}
//2.找到i位置的节点
Node curr = temp.next;
//3.创建新节点
Node newNode = new Node(t,temp,curr);
//4.让i位置的前一个节点的next指向新节点
temp.next = newNode;
//5.让i位置节点的pre指向新节点
curr.pre = newNode;
//6.元素个数加1
length++;
}
//删除并返回链表中第i个数据元素
public T remove(int i ){
//1.找到i位置的前一个节点
Node temp = head;
for(int index = 0;index<i;index++){
temp = temp.next;
}
//2.找到i位置的节点
Node currNode = temp.next;
//3.找到i位置的后一个节点
Node nextNode = currNode.next;
//4.让i位置的前一个节点的next指向i位置的后一个节点
temp.next = nextNode;
//5.让i位置的后一个节点的pre指向i位置的前一个节点
nextNode.pre = temp;
//5.元素个数减1
length--;
return currNode.data;
}
//显示链表
public void showList(){
//判断链表是否为空
if(isEmpty()){
System.out.println("链表为空");
return;
}
//因为头节点不能动,用temp用来辅助遍历
Node temp = head;
while (temp.next!=null){
temp = temp.next;
System.out.println("\t"+temp.data);
}
}
//获取第一个元素
public T getFirst(){
if(isEmpty()){
return null;
}
return head.next.data;
}
//获取最后一个元素
public T getLast(){
if(isEmpty()){
return null;
}
return last.data;
}
//1.节点类
private class Node{
//存储数据
public T data;
//指向上一个节点
public Node pre;
//指向下一个节点
public Node next;
public Node(T data, Node pre, Node next) {
this.data = data;
this.pre = pre;
this.next = next;
}
}
//实现Iterable后重写的方法,因为这个方法需要返回的是Iterator类型
//而Iterator是一个接口
//所以我们写一个实现Iterator接口的实现类
@Override
public Iterator<T> iterator() {
return new Titerator();
}
//Iterator实现类
private class Titerator implements Iterator{
private Node node;
public Titerator(){
this.node = head;
}
@Override
public boolean hasNext() {
//返回是否有下一个节点 true:有 false:没有
return node.next!=null;
}
@Override
public Object next() {
//返回下一个节点的数据
node = node.next;
return node.data;
}
}
}
为了外部方便遍历实现了Iterable接口
5.3测试代码及效果
public static void main(String[] args) {
//创建双向链表
DoubleLinkedList<String> linkedList = new DoubleLinkedList<>();
//测试数据插入
linkedList.insert("孙悟空");
linkedList.insert("猪八戒");
linkedList.insert("沙僧");
linkedList.insert("唐僧");
//测试是否为空
System.out.println("是否为空:"+linkedList.isEmpty());
//测试获取个数
System.out.println("链表元素个数:"+linkedList.length());
//测试获取
System.out.println("1位置获取到的元素:"+linkedList.get(1));
//测试指定数据首次出现位置
System.out.println("孙悟空第一次出现位置:"+linkedList.indexOf("孙悟空"));
//测试指定位置插入插入元素
linkedList.insert(1,"白龙马");
//测试遍历
System.out.println("插入白龙马后的遍历结果:");
linkedList.showList();
//测试删除
System.out.println("成功删除:"+linkedList.remove(1));
//测试获取第一个元素
System.out.println("第一个元素:"+linkedList.getFirst());
//测试获取最后一个元素
System.out.println("最后一个元素:"+linkedList.getLast());
}
6.单向环形链表
循环链表,顾名思义,链表整体要形成一个圆环状。在单向链表中,最后一个节点的指针为null,不指向任何节点,因为没有下一个元素了。要实现循环链表,我们只需要让单向链表的最后一个节点的指针指向第一个节点即可。
6.1单向环形链表的创建
package com.lzf.linkedlist2;
/**
* 单向环形链表
*/
public class LoopLinkedList {
public static void main(String[] args) {
//创建节点
Node<String> n1 = new Node<>("孙悟空",null);
Node<String> n2 = new Node<>("猪八戒",null);
Node<String> n3 = new Node<>("沙僧",null);
Node<String> n4 = new Node<>("唐僧",null);
//构建单向链表
n1.next = n2;
n2.next = n3;
n3.next = n4;
//构建单向环形链表,将最后一个节点指向第一个节点即可
n4.next = n1;
}
}
//节点类
class Node<T>{
//储存数据
T data;
//指向下一个几点
Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
7.约瑟夫问题
问题描述:
据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。于是Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
问题转换:
41个人坐一圈,第一个人编号为1,第二个人为2,第n个人的编号为n。
- 编号为1的人开始从1报数,依次向后,报数为3的那个人出圈
- 自退出那个人开始的下一个人再次从1开始报数,以此类推
- 求最后退出的那个人的编号(最后出圈的人就不用si了)
图示:
解题思路:
- 构建含有41个节点的单向循环链表,分别存储1-41的值,分别代表这41个人
- 使用计数器count,记录当前报数的值
- 遍历链表,每循环一次count++
- 判断count的值,如果是3,则从链表中删除这个节点并打印节点的值,把count重置为0
上一篇: 主动和我说话的就是过度勾引
下一篇: 8个承认