目录
一、单项列表
二、双向列表
三、约瑟夫问题(单项列表)
一、单项列表
链表的优点：
由于链表上的元素在空间存储上内存地址不连续。
所以随机增删元素的时候不会有大量元素位移，因此随机增删效率较高。
在以后的开发中，如果遇到随机增删集合中元素的业务比较多时，建议
使用linkedList。
链表的缺点：
不能通过数学表达式计算被查找元素的内存地址，每一次查找都是从头
节点开始遍。
注意:
public class ListNode{
int val;
ListNode next; //链表指向的下一个值的指针
ListNode(int x){val = x;} //这个方式赋值
}
通过xx.next = new ListNode(4);来赋值，注意此时是赋值给下一个指针指向的位置,此时此链表一个值，值为4。
单项列表例子
package linked;
public class GoodsNode {
public int id;
public String name;
public Double price;
@Override
public String toString() {
return "GoodsNode{" +
"id=" + id +
", name='" + name + ''' +
", price=" + price +
'}';
}
public GoodsNode next;
public GoodsNode(int id, String name, Double price) {
this.id = id;
this.name = name;
this.price = price;
}
}
package linked;
public class DLlinkedList {
GoodsNode node = new GoodsNode(0, "", 0.0);
//往链表中插入数据(在最后插入)
public void add(GoodsNode goodsNode) {
GoodsNode temp = node;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = goodsNode;
}
//添加节点(按照顺序)
//按照商品id进行排序，从小到达按顺序添加
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;
}
}
//修改节点
//1、直到链表中的最后—个节点未找到，则结束循环
//2、找到了节点，结束循环
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 delNode(int id) {
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;
while (true){
if(temp==null){
break;
}
System.out.println(temp);
temp=temp.next;
}
}
}
public class linkedTest {
public static void main(String[] args) {
DLlinkedList linkedList = new DLlinkedList();
GoodsNode goodsNode1 = new GoodsNode(1,"耐克运动鞋",599.00);
GoodsNode goodsNode2 = new GoodsNode(2,"耐克上衣",399.00);
GoodsNode goodsNode3 = new GoodsNode(3,"阿迪达斯运动鞋",699.00);
GoodsNode goodsNode4 = new GoodsNode(4,"李宁运动鞋",499.00);
linkedList.addOrder(goodsNode3);
linkedList.addOrder(goodsNode1);
linkedList.addOrder(goodsNode2);
linkedList.addOrder(goodsNode4);
linkedList.list();
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
linkedList.updateNode(new GoodsNode(1,"新科技鞋子",1999.9));
linkedList.list();
System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
linkedList.delNode(1);
linkedList.list();
}
}
二、双向列表
双向列表例子
public class BookNode {
public int id;
public String name;
public double price;
public BookNode next;
public BookNode pre;
public BookNode(int id, String name, double price) {
this.id = id;
this.name = name;
this.price = price;
}
@Override
public String toString() {
return "DuallinkedList{" +
"id=" + id +
", name='" + name + ''' +
", price=" + price +
'}';
}
}
public class DuallinkedList {
BookNode head = new BookNode(0, "", 0);
//添加结尾新的节点
public void addLast(BookNode newNode) {
BookNode temp = head;
while (true) {
//如果第一次进入，表示双向链表是空数据
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = newNode;
newNode.pre = temp;
}
//根据顺序添加新的列表
public void addOrder(BookNode newNode) {
BookNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.id>newNode.id) {
break;
} else if (temp.id == newNode.id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
System.out.println("该书已存在");
} else {
if(temp.next!=null){
newNode.next=temp.next;
temp.next.pre=newNode;
temp.next=newNode;
newNode.pre=temp;
}else {
temp.next=newNode;
newNode.pre=temp;
}
}
}
//修改节点
public void updateNode(BookNode node) {
if (head.next == null) {
System.out.println("空链表");
return;
}
BookNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.id == node.id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = node.name;
temp.price = node.price;
} else {
System.out.println("未找到修改的节点");
}
}
//删除节点
public void delNode(BookNode node) {
if (head.next == null) {
System.out.println("双向链表为空");
return;
}
BookNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.id == node.id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.pre.next = temp.next;
if (temp.next != null) {
temp.next.pre = temp.pre;
}
}
}
public void list() {
if (head.next == null) {
System.out.println("空链表");
return;
}
BookNode temp = head.next;
while (true){
if(temp==null){
break;
}
System.out.println(temp);
temp=temp.next;
}
}
}
public class Test {
public static void main(String[] args) {
DuallinkedList duallinkedList = new DuallinkedList();
BookNode bookNode1= new BookNode(1,"红楼梦",66.0);
BookNode bookNode2= new BookNode(2,"西游记",66.0);
BookNode bookNode3= new BookNode(3,"水浒传",66.0);
BookNode bookNode4= new BookNode(4,"三国演义",66.0);
duallinkedList.addOrder(bookNode3);
duallinkedList.addOrder(bookNode1);
duallinkedList.addOrder(bookNode2);
duallinkedList.addOrder(bookNode4);
duallinkedList.list();
}
}
三、约瑟夫问题(单项列表)
约瑟夫问题的示意
osephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下
构建环形链表
约瑟夫问题代码展示
//节点的对象
public class Boy {
//结点编号
private int no;
//指向下一个节点
private Boy next;
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
public class CircleSinglelinkedLList {
private Boy first = new Boy(-1);
//构建环形链表
public void addBoy(int nums){
if(nums<1){
System.out.println("数据不正确");
return;
}
Boy temp =null;
for(int i = 1;i<=nums;i++){
Boy boy = new Boy(i);
//判断是否是第一个小孩
if(i==1){
first= boy;
first.setNext(first);
temp=first;
}else{
temp.setNext(boy);
boy.setNext(first);
temp=boy;
}
}
}
//查看环形链表中的节点
public void showBoy(){
if(first==null){
System.out.println("链表为空");
return;
}
Boy boy =first;
while (true){
System.out.printf("小孩的编号%dn",boy.getNo());
if(boy.getNext()==first){
break;
}
boy = boy.getNext();
}
}
//当调用该方法输入第几个小孩子数数，数几次，环形链表中一共几个小孩
public void countBoy(int startNo,int countNum,int nums ){
if(first==null||startNo<1||startNo>nums){
System.out.println("参数输入有错");
return;
}
//定义辅助指点，指向的是环形单链表中的最后一个节点
Boy helper = first;
while (true){
if(helper.getNext()==first){
break;
}
helper=helper.getNext();
}
//寻找起始位置，把first定义为起始位置
for(int j =0;j
public class TestBoy {
public static void main(String[] args) {
CircleSinglelinkedLList circleSinglelinkedLList = new CircleSinglelinkedLList();
circleSinglelinkedLList.addBoy(5);
circleSinglelinkedLList.showBoy();
circleSinglelinkedLList.countBoy(1,2,5);
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）