- 方式三、
什么是链表
-
链表（linked list）是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）；
-
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活；
-
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
- 表元素域elem用来存放具体的数据；
- 链接域next用来存放下一个节点的位置 ；
- 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
代码实现《单向链表》
package com.daley.linkedlist;
import java.util.Iterator;
class Test{
public static void main(String[] args) {
MylinkedList
单向链表的案例
-
单链表的反转【腾讯面试题】
// 单链表的反转【腾讯面试题】
// 方式一、 递归方式翻转
public void reverse1(){
//判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
if (isEmpty()){
return;
}
reverse(head.next);
}
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;
}
方式二
-
从尾到头打印单链表 【百度面试题】
方式 1：反向遍历(这里就不写代码了，和前一个基本一样)
方式 2：Stack 栈 （利用栈的先进后出的特点，来实现逆序打印效果）
单链表的一个变形是单向循环链表，链表中最后一个节点的next域不再为null，而是指向链表的头节点。
单线无头循环链表代码实现
public class MyHeadlesslinkedList{ // 虽然没有头部但是依旧需要使用一个字段来记录第一个值 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; } public boolean isEmpty(){ return this.N == 0; } public int length(){ return this.N; } 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; } 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 ++; } 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 ++; } 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; } 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; } }
案例使用 约瑟夫问题
问题描述：
传说有这样一个故事，在罗马人占领乔塔帕特后，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) {
int S=41;
int F=1;
int N=3;
MyHeadlesslinkedList iml = new MyHeadlesslinkedList();
for (int i = 1; i <= S; i++) {
iml.insert(i);
}
MyHeadlesslinkedList.Node node = iml.getNode(F-1); // 因为下标零开始所以 F-1
MyHeadlesslinkedList.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. 双向链表
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
直接上代码
public class TowWaylinkedListimplements 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; } public boolean isEmpty(){ return this.N==0; } public int length(){ return this.N; } public T get(int indix){ Node node = this.head; for (int i = 0; i < indix; i++) { node = node.next; } return node.item; } 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++; } 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++; } 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; } 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; } public T getFirst(){ if(isEmpty()){ return null; } return this.head.item; } public T getLast(){ if(isEmpty()){ return null; } return this.last.item; } @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. 链表与顺序表的对比
链式存储结构的优点:
- 结点空间可以动态申请和释放。
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。
链式存储结构的缺点:
- 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
- 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。
