四、Java数据结构-链表(LinkedList)
2021-03-31 本文已影响0人
daley_磊
什么是链表
-
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）；
-
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活；
-
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
1. 单向链表
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
- 表元素域
elem用来存放具体的数据； - 链接域
next用来存放下一个节点的位置 ； - 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
代码实现《单向链表》
| 类名 | MyLinkedList |
|---|---|
| 成员方法 | 1.public void clear()：清空链表 2.publicboolean isEmpty()：判断链表是否为空，是返回true，否返回false 3.public int length():获取链表中元素的个数 4.public T get(int i):读取并返回链表中的第i个元素的值 5.public void insert(T t)：往链表中添加一个元素； 6.public void insert(int i,T t)：在链表的第i个元素之前插入一个值为t的数据元素。 7.public T remove(int i):删除并返回链表中第i个数据元素。 8.public int indexOf(T t):返回链表中首次出现的指定的数据元素的位序号，若不存在，则返回-1 |
| 成员内部类 | private class Node:结点类 |
| 成员变量 | 1.private Node head:记录首结点 2.private int N:记录链表的长度 |
package com.daley.linkedlist;
import java.util.Iterator;
class Test{
public static void main(String[] args) {
MyLinkedList<Object> ml = new MyLinkedList<>();
ml.insert("aa");
ml.insert("bb");
ml.insert("cc");
ml.insert(0,"dd");
for (Object s : ml){
System.out.println(s);
}
}
}
public class MyLinkedList<T> implements Iterable<T> {
//记录头结点
private Node head;
//记录链表的长度
private int N;
public MyLinkedList(){
this.head = new Node(null,null);
this.N = 0;
}
/**
* 定义节点类
*/
private class Node{
T item ; //存储数据
Node next; //下一个节点
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
/**
* 清空链表
*/
public void clear(){
this.head = null;
this.N = 0;
}
/**
* 判断链表是否为空，是返回true，否返回false
* @return
*/
public boolean isEmpty(){
return this.N == 0;
}
/**
* 获取链表中元素的个数
* @return
*/
public int length(){
return this.N;
}
/**
* 读取并返回链中的第index个元素的值
* @param index
* @return
*/
public T get(int index){
if(index > this.N){
System.out.println("链表长度越界！");
return null;
}
Node n = this.head;
for (int i = 0; i < index; i++) {
n = n.next;
}
return n.item;
}
/**
* 往链表中添加一个元素
* @param t
*/
public void insert(T t){
Node n = this.head;
while (n.next != null){
n=n.next;
}
//让当前最后一个结点指向新结点
n.next = new Node(t, null);
N ++;
}
/**
* 在链表的第index个元素之前插入一个值为t的数据元素
* @param index
* @param t
*/
public void insert(int index,T t){
//找到index位置前一个结点
Node pre = this.head;
for (int i = 0; i <= index - 1 ; i++) {
pre = pre.next;
}
//要找到index位置的结点
Node curr = pre.next;
pre.next = new Node(t,curr);
this.N ++;
}
/**
* 删除并返回链表中第i个数据元素
* @param index
* @return
*/
public T remove(int index){
//找到index位置前一个结点
Node pre = this.head;
for (int i = 0; i < index ; i++) {
pre = pre.next;
}
//要找到index位置的结点
Node curr = pre.next;
//找到index位置的下一个结点
Node nextNode = curr.next;
pre.next = nextNode;
this.N --;
return curr.item;
}
/**
*返回链表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
* @param t
* @return
*/
public int indexOf(T t){
Node pre = this.head;
int count = 0;
while (pre.next!=null){
count ++ ;
pre = pre.next;
if(pre.item.equals(t)){
return count;
}
}
return -1;
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator{
private Node n;
public MyIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
}
单向链表的案例
-
单链表的反转【腾讯面试题】
- 方式一(递归方式反转链表
推荐)
// 单链表的反转【腾讯面试题】
// 方式一、 递归方式翻转
/**
* 用来反转整个链表
*/
public void reverse1(){
//判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
if (isEmpty()){
return;
}
reverse(head.next);
}
/**
* 反转指定的结点curr，并把反转后的结点返回
* @param curr
* @return
*/
public Node reverse(Node curr){ // aa bb cc
if (curr.next==null){
head.next=curr;
return curr;
}
//递归的反转当前结点curr的下一个结点；返回值就是链表反转后，当前结点的上一个结点
Node pre = reverse(curr.next);
//让返回的结点的下一个结点变为当前结点curr；
pre.next=curr;
//把当前结点的下一个结点变为null
curr.next=null;
return curr;
}
- 方式二
// 方式二、创建一个新的 链表，循环往第一个值插入，返回一个新链表
public MyLinkedList<T> reverse2(){
Node pre = this.head;
MyLinkedList<T> ml2 = new MyLinkedList<>();
while (pre.next != null){
pre = pre.next;
ml2.insert(0,pre.item);
}
return ml2;
}
-
从尾到头打印单链表 【百度面试题】
方式 1：反向遍历(这里就不写代码了，和前一个基本一样)
方式 2：Stack 栈 （利用栈的先进后出的特点，来实现逆序打印效果）
public void reverseStackPrint(){
Node pre = this.head;
Stack stack = new Stack();
while (pre.next != null){
pre = pre.next;
stack.push(pre.item);
}
while (!stack.isEmpty()){
System.out.println(stack.pop());
}
}
2. 单向循环链表
单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为null，而是指向链表的头节点。
单向循环链表
单线无头循环链表代码实现
| 类名 | MyHeadlessLinkedList |
|---|---|
| 成员方法 | 1.public void clear()：清空链表 2.publicboolean isEmpty()：判断链表是否为空，是返回true，否返回false 3.public int length():获取链表中元素的个数 4.public T get(int i):读取并返回链表中的第i个元素的值 5.public T getNode(int i):读取并返回链表中的第i个元素的Node 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 int indexOf(T t):返回链表中首次出现的指定的数据元素的位序号，若不存在，则返回-1 |
| 成员内部类 | private class Node:结点类 |
| 成员变量 | 1.private Node head:记录首结点 2.private int N:记录链表的长度 |
package com.apricot.MyHeadlessLinkedList;
import java.util.Iterator;
/**
* @ClassNmae MyHeadlessLinkedList
* @Description TODO
* @Author L.D
* @Date 2022/2/23 22:23
**/
class Test{
public static void main(String[] args) {
MyHeadlessLinkedList<Object> ml = new MyHeadlessLinkedList<>();
ml.insert("aa");
ml.insert("bb");
ml.insert("cc");
ml.insert(0,"dd");
ml.insert(1,"rr");
for (int i = 0; i < ml.length(); i++) {
System.out.println(ml.get(i));
}
}
}
public class MyHeadlessLinkedList<T> implements Iterable<T>{
// 虽然没有头部但是依旧需要使用一个字段来记录第一个值
private Node head;
//记录链表的长度
private int N;
public MyHeadlessLinkedList(){
}
/**
* 定义节点类
*/
public class Node{
T item ; //存储数据
Node next; //下一个节点
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
/**
* 清空链表
*/
public void clear(){
this.head = null;
this.N = 0;
}
/**
* 判断链表是否为空，是返回true，否返回false
* @return
*/
public boolean isEmpty(){
return this.N == 0;
}
/**
* 获取链表中元素的个数
* @return
*/
public int length(){
return this.N;
}
/**
* 读取并返回链表中的第index个元素的值
* @param index
* @return
*/
public T get(int index){
if(index > this.N){
System.out.println("链表长度越界！");
return null;
}
Node n = this.head;
for (int i = 0; i < index; i++) {
n = n.next;
}
return n.item;
}
public Node getNode(int index){
if(index > this.N){
System.out.println("链表长度越界！");
return null;
}
Node n = this.head;
for (int i = 0; i < index; i++) {
n = n.next;
}
return n;
}
/**
* 往链表中添加一个元素
* @param t
*/
public void insert(T t){
if(isEmpty()){
this.head = new Node(t, null);
}
Node n = this.head;
for (int i = 1; i < this.N ; i++) {
n=n.next;
}
//让当前最后一个结点指向新结点
n.next = new Node(t, this.head);
N ++;
}
/**
* 在链表的第index个元素之前插入一个值为t的数据元素
* @param index
* @param t
*/
public void insert(int index,T t) {
//找到index位置前一个结点
Node pre = this.head;
if (index == 0) {
this.head = new Node(t, pre);
} else {
for (int i = 1; i <= index-1 ; i++) {
pre = pre.next;
}
//要找到index位置的结点
Node curr = pre.next;
pre.next = new Node(t, curr);
}
this.N++;
}
/**
* 删除并返回链表中第i个数据元素
* @param index
* @return
*/
public T remove(int index){
//找到index位置前一个结点
Node curr = null;
if(index == 0){ // index 为0时表示需要重新处理head
curr = head;
head = head.next;
}else {
Node pre = this.head;
for (int i = 0; i < index - 1 ; i++) {
pre = pre.next;
}
//要找到index位置的结点
curr = pre.next;
//找到index位置的下一个结点
pre.next = curr.next;
}
this.N --;
return curr.item;
}
/**
*返回链表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
* @param t
* @return
*/
public int indexOf(T t){
Node pre = this.head;
int count = 0;
while (pre.next!=null){
count ++ ;
pre = pre.next;
if(pre.item.equals(t)){
return count;
}
}
return -1;
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator{
private Node n;
public MyIterator(){
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n = n.next;
return n.item;
}
}
}
案例使用 约瑟夫问题
问题描述：
传说有这样一个故事，在罗马人占领乔塔帕特后，39 个犹太人与约瑟夫及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，第一个人从1开始报数，依次往后，如果有人报数到3，那么这个人就必须自杀，然后再由他的下一个人重新从1开始报数，直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是，约瑟夫要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，从而逃过了这场死亡游戏。
问题转换：
- 41个人坐一圈，第一个人编号为1，第二个人编号为2，第n个人编号为n。
- 编号为1的人开始从1报数，依次向后，报数为3的那个人退出圈；
- 自退出那个人开始的下一个人再次从1开始报数，以此类推；
- 求出最后退出的那个人的编号。
解题思路：
- 构建含有41个结点的单向循环链表，分别存储1~41的值，分别代表这41个人；
- 使用计数器count，记录当前报数的值；
- 遍历链表，每循环一次，count++；
- 判断count的值，如果是3，则从链表中删除这个结点并打印结点的值，把count重置为0
代码实现
- 方式一（链表实现）、
public static void main(String[] args) {
/*
* "约瑟夫环"问题
* 共S个人，从第F个人开始报数，报数1—N
* 这里初始化的41个，人从第1个开始报数，数到3的出局
* S 为人数 ，F 为开始人的编号 ，N为需要走的个数
* 最后运行结果：3,6,9,12,15,18,21,24,27,30,33,36,39,1,5,10,14,19,23,28,32,37,41,7,13,20,26,34,40,8,17,29,38,11,25,2,22,4,35,16,31
*/
int S=41;
int F=1;
int N=3;
MyHeadlessLinkedList<Integer> iml = new MyHeadlessLinkedList<Integer>();
for (int i = 1; i <= S; i++) {
iml.insert(i);
}
MyHeadlessLinkedList<Integer>.Node node = iml.getNode(F-1); // 因为下标零开始所以 F-1
MyHeadlessLinkedList<Integer>.Node temp=null;
int count = 0 ;
while (node.next != node){ //当自己与自己的next相等时，表示剩最后一个了停止循环
count++ ;
if(count == N ){
temp.next = node.next;
System.out.print(node.item+",");
count = 0;
}else {
temp = node;
}
node = node.next;
}
System.out.println(node.item+"\n");
}
- 方式二、
public static void main(String args[]) {
final int N=41,S=1,M=3;
int i = S-1, k = N, g = 1, j;
int a[] = new int[N]; //使用数组存放人;
for(int h = 1; h <= N; h++){
a[h-1] = h; //将编号为h的人存到下标为h-1的数组中
}
do {
i = i + (M -1) ; //计算出圈人下标,因为自身需要报数所以减一
while(i >= k)
i = i-k;
System.out.print(a[i]+",");
j = i;
while ( j < k-1) {
a[j] = a[j+1]; //第i个人出圈后将后面的人的编号往前移动,相当于把数到5的踢出局
j++;
}
k--; //圈中人数k-1
g++; //循环次数g+1
}while(g <= N); //最多N轮循环
}
- 方式三、
public static void main(String args[]) {
final int N = 41, S = 1, M = 3; //N为总人数，从第S个人开始报数，报数到M的为出圈
int a[] = new int[N + 1];
int i, j, k;
k = S - 1; //k等于S-1，表示从S开始数出圈人的下标
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) {
if (k == N)
k = 1; //当出圈人的下标到末尾时，记数从1开始
else
k++;
if (a[k] == 1) //a[k] 做标记，说明下标为k的人已经出圈了
j--; //j-1, 以保证每次数超过M个
}
a[k] = 1; //标记出圈
System.out.print((k) + ","); //下标为k的人标号为k
}
}
3. 双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
双向链表
直接上代码
| 类名 | TowWayLinkedList |
|---|---|
| 成员方法 | 1.public void clear()：空置链表 2.public boolean isEmpty()：判断链表是否为空，是返回true，否返回false; 3.public int length():获取链表中元素的个数; 4.public T get(int i):读取并返回链表中的第i个元素的值; 5.public void insert(T t)：往链表中添加一个元素； 6.public void insert(int i,T t)：在链表的第i个元素之前插入一个值为t的数据元素; 7.public T remove(int i):删除并返回链表中第i个数据元素; 8.public int indexOf(T t):返回链表中首次出现的指定的数据元素的位序号，若不存在，则返回-1; 9.public T getFirst():获取第一个元素; 10.public T getLast():获取最后一个元素; |
| 成员内部类 | private class Node:结点类; |
| 成员变量 | 1. private Node first:记录首结点; 2. private Node last:记录尾结点; 3. private int N:记录链表的长度; |
public class TowWayLinkedList<T> implements Iterable{
// 首节点
private Node head;
// 尾节点
private Node last;
// 链表长度
private int N;
public TowWayLinkedList(){
this.head = new Node(null,null,null);
this.last = null;
this.N = 0;
}
class Node {
T item;
Node next;
Node pre;
public Node(T item,Node next,Node pre){
this.item = item;
this.next = next;
this.pre = pre;
}
}
/**
* 空置链表
*/
public void clear(){
this.last = null;
this.head = new Node(null,null,null);
this.N = 0;
}
/**
* 判断链表是否为空，是返回true，否返回false
* @return
*/
public boolean isEmpty(){
return this.N==0;
}
/**
* 获取链表中元素的个数;
* @return
*/
public int length(){
return this.N;
}
/**
* :读取并返回链表中的第i个元素的值
* @param indix
* @return
*/
public T get(int indix){
Node node = this.head;
for (int i = 0; i < indix; i++) {
node = node.next;
}
return node.item;
}
/**
* 往链表中添加一个元素
* @param t
*/
public void insert(T t){
if(this.last==null){
last = new Node(t,null,head);
head.next = last;
}else{
Node oldLast = this.last;
Node node = new Node(t,null,oldLast);
oldLast.next = node;
last = node;
}
N++;
}
/**
* 在链表的第i个元素之前插入一个值为t的数据元素
* @param index
* @param t
*/
public void insert(int index,T t){
Node node = this.head;
// 获取需要插入数据的上一个节点
for (int i = 0; i < index; i++) {
node = node.next;
}
// 当前节点
Node curr = node.next;
// 需要插入的节点，上一个节点为原来的上一个节点，下一个节点是当前节点的位置
Node newNode = new Node(t, curr, node);
// 上一个节点的next标记为新增节点
node.next = newNode;
// 当前节点往后移以为，上一个节点标记为新增节点
curr.pre = newNode;
N++;
}
/**
*删除并返回链表中第i个数据元素;
* @param index
* @return
*/
public T remove(int index){
Node node = this.head;
// 获取需要插入数据的上一个节点
for (int i = 0; i < index; i++) {
node = node.next;
}
// index当前节点
Node curr = node.next;
// index 下一个节点
Node currNext = curr.next;
// 上一个节点的next标记为index的下一个节点
node.next = currNext;
// index 下一个节点的pre标记为index的上一个节点
currNext.pre = node;
N--;
return curr.item;
}
/**
* 返回链表中首次出现的指定的数据元素的位序号，若不存在，则返回-1
* @param t
* @return
*/
public int indexOf(T t){
Node node = this.head;
// 获取需要插入数据的上一个节点
int count = 0;
while (node.next != null) {
node = node.next;
if(node.item.equals(t)){
return count;
}
count ++;
}
return -1;
}
/**
* 获取第一个元素
* @return
*/
public T getFirst(){
if(isEmpty()){
return null;
}
return this.head.item;
}
/**
* 获取最后一个元素;
* @return
*/
public T getLast(){
if(isEmpty()){
return null;
}
return this.last.item;
}
/**
* 为方便forEach 循环 重写iterator方法
* @return
*/
@Override
public Iterator iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator{
Node node = head;
@Override
public boolean hasNext() {
return node.next != null;
}
@Override
public Object next() {
node = node.next;
return node.item;
}
}
}
4. 链表与顺序表的对比
链式存储结构的优点:
- 结点空间可以动态申请和释放。
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
链式存储结构的缺点:
- 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
- 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。
