链表 - 阿权呐

单向链表：

链表是一种在物理地址中非连续，非顺序的存储结构，数据逻辑通过链表中的指针链接实现的。

单链表应用：根据带有头部的单链表，实现商品增删改查，并且也可以针对商品已编号进行排序。

GoodsNode.java

package pers.quan.linked.singlelilnked;

public class GoodsNode {
    private String name;
    private int id;
    private double price;
    public GoodsNode next;

    public GoodsNode(String name, int id, double price) {
        this.name = name;
        this.id = id;
        this.price = price;
    }

    public GoodsNode() {

    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    public GoodsNode getNext() {
        return next;
    }

    public void setNext(GoodsNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "GoodsNode{" +
                "name='" + name + '\'' +
                ", id=" + id +
                ", price=" + price +
                ", next=" + next +
                '}';
    }
}

MyLinked.java ：实现代码

package pers.quan.linked.singlelilnked;

public class MyLinked {

//    头指针
    private GoodsNode goodsNodeHead = new GoodsNode("",0,0.0);

    /**
     * 顺序插入
     * @param goodsNode
     */
    public void insert(GoodsNode goodsNode) {
        GoodsNode temp = goodsNodeHead;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = goodsNode;
    }

    /**
     * 按照id插入，顺序从小到大
     * @param node
     */
    public void insertByIdNode(GoodsNode node) {
        GoodsNode temp = goodsNodeHead;
        boolean flag = false;
        while(true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.getId() > node.getId()) {
                break;
            }
            if (temp.next.getId() == node.getId()) {
                flag = true;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("要插入的节点已存在");
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    /**
     * 修改节点
     * 根据id修改
     * @param node
     */
    public void modifyNode(GoodsNode node) {
        GoodsNode temp = goodsNodeHead;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.getId() == node.getId()) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if(flag) {
            temp.setName(node.getName());
            temp.setPrice(node.getPrice());
        } else {
            System.out.println("没有找到该节点");
        }
    }

    /**
     * 根据id删除节点
     */
    public void deleteNode(GoodsNode node) {
        GoodsNode temp = goodsNodeHead;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.getId() == node.getId()) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        }
    }

    /**
     * 查询链表中所有的元素
     */
    public void selectAll() {
        GoodsNode temp = goodsNodeHead;
        while (true) {
            if (temp==null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

MyLinedTest.java 对上面的代码进行测试：

package pers.quan.linked.singlelilnked;

public class MyLinkedTest {
    
    public static void main(String[] args) {
        GoodsNode goods1 = new GoodsNode("安踏", 1, 199.99);
        GoodsNode goods2 = new GoodsNode("耐克", 2, 299.99);
        GoodsNode goods3 = new GoodsNode("李宁", 3, 189.00);

        MyLinked myLinked = new MyLinked();
//      顺序插入
//        myLinked.insert(goods2);
//        myLinked.insert(goods3);
//        myLinked.insert(goods1);
//       按照id大小排序插入
        myLinked.insertByIdNode(goods2);
        myLinked.insertByIdNode(goods1);
        myLinked.insertByIdNode(goods3);

//        修改
        myLinked.modifyNode(new GoodsNode("杂牌",2,9.9));
        myLinked.selectAll();
        System.out.println("-------------");
//        删除
        myLinked.deleteNode(new GoodsNode("",3,0));
        myLinked.selectAll();
    }
}

双向链表：

Pre：前驱节点 Next：后继节点

从链表的任何一个节点开始，都可以访问到它的前一个和后一个节点元素。

使用双向链表实现对书籍的添加删除等：

Books.java

package pers.quan.linked.bothwaylinked;

public class Books {
    private String name;
    private int id;
    private double price;
    private Books pre; // 前驱节点
    private Books next; // 后继节点

    public Books(String name, int id, double price) {
        this.name = name;
        this.id = id;
        this.price = price;
    }
    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    public Books getPre() {
        return pre;
    }

    public void setPre(Books pre) {
        this.pre = pre;
    }

    public Books getNext() {
        return next;
    }

    public void setNext(Books next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Books{" +
                "name='" + name + '\'' +
                ", id=" + id +
//                ", pre=" + pre +  这个不能打印出来，会造成递归栈溢出
                ", next=" + next +
                '}';
    }
}

MybothwayLinked.java ：实现代码

package pers.quan.linked.bothwaylinked;

/**
 * 双链表
 */
public class MybothwayLinked {

//    头节点
    private Books head = new Books("",0,0.0);

    /**
     * 尾部添加节点
     * @param book
     */
    public void insertLast(Books book) {
        Books temp = head;
        while (true){
            if (temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(book);
        book.setPre(temp);
    }

    /**
     * 修改节点，根据id
     * @param book
     */
    public void modifyNode(Books book) {
        Books temp = head;
        boolean flag = false;
        while (true) {
            if (temp.getNext() == null) {
                break;
            }
            if (temp.getId() == book.getId()) {
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag) {
            temp.setName(book.getName());
            temp.setPrice(book.getPrice());
        } else {
            System.out.println("是一个空的链表");
        }
    }

    /**
     * 删除节点，通过id
     * @param book
     */
    public void deleteNode(Books book) {
        Books temp = head;
        boolean flag = false;
        while (true) {
            if (temp.getNext() == null) {
                break;
            }
            if (temp.getId() == book.getId()) {
                flag =  true;
                break;
            }
            temp = temp.getNext();
        }
        if(flag) {
            temp.getPre().setNext(temp.getNext());
//            判断是否为最后一个元素
            if(temp.getNext() != null) {
                temp.getNext().setPre(temp.getPre());
            }
            System.out.println("删除成功");
        } else {
            System.out.println("是一个空的链表1");
        }
    }



    /**
     * 按照id大小添加
     */
    public void insertById(Books book) {


    }

//    打印出来
    public void printLikendList() {
        Books temp = head;
        if (temp.getNext() == null) {
            return;
        }
        System.out.println(temp.getNext());
    }


    /**
     * 返回链表元素的长度
     * @return
     */
    public int getlen() {
        Books temp = head;
        int count = 0;
        if (temp.getNext() == null) {
            return 0;
        }

        while (true) {
            if (temp.getNext() == null) {
                break;
            }
            count++;
            temp = temp.getNext();
        }
        return count;
    }

}

MybothwayLinkedTest.java 对上面的代码进行测试

package pers.quan.linked.bothwaylinked;

public class MybothwayLinkedTest {

    public static void main(String[] args) {
        Books book1 = new Books("Java程序设计", 1, 10.9);
        Books book2 = new Books("数据结构和算法", 2, 10.9);
        Books book3 = new Books("计算机组成原理", 3, 10.9);
        Books book4 = new Books("操作系统", 4, 10.9);

        MybothwayLinked mybothwayLinked = new MybothwayLinked();
        mybothwayLinked.insertLast(book1);
        mybothwayLinked.insertLast(book2);
        mybothwayLinked.insertLast(book3);
        mybothwayLinked.insertLast(book4);

//      修改
        mybothwayLinked.modifyNode(new Books("计算机网络",1,188.88));
//      删除
        mybothwayLinked.deleteNode(new Books("",3,0.0));
//      打印里面的元素
        mybothwayLinked.printLikendList();
//        查看链表的元素个数
        System.out.println(mybothwayLinked.getlen());
    }
}

文章目录

单向链表：
双向链表：

链表

单向链表：

双向链表：

评论已关闭

热门文章

最新文章

最近回复

分类

标签

归档

其它