亲宝软件园·资讯

展开

【数据结构和算法】001 单链表 LinkedList

LiPro 人气:0

 

 

 

 

 


 

一、单链表(LinkedList)介绍和内存布局

链表是有序的列表,它在内存中的实际存储结构如下:

     

 

 看上去虽然无序,但他是靠灭个链表节点元素的地址和next域来分清首尾相连的顺序,如下图所示,由头指针指向第一个元素,进而第二个、三个...

  

 链表的逻辑结构:

 

 

 

 

二、单链表创建、遍历实现以及单链表节点增、删、改、查操作

 

1、创建、新增、遍历显示

模型如下:1)head节点 2)中间节点 3)尾结点

                 每个节点的next域指向下一个节点的对象地址,尾结点为空

 

 

创建


 新建所需实体类:

package ...;

/**
 * @Author: ldk
 * @Date: 2020/3/29 21:18
 * @Describe:
 */
public class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一个节点

    //构造节点对象
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    //重写toString()

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }

}

创建 SingleLinkedList 类,编写添加和遍历的方法:

创建main方法测试:

package ...;

/**
 * @Author: ldk
 * @Date: 2020/3/29 21:25
 * @Describe:
 */
public class LinkedListTest {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "张三", "小三");
        HeroNode h2 = new HeroNode(2, "李四", "小四");
        HeroNode h3 = new HeroNode(3, "王五", "小五");
        HeroNode h4 = new HeroNode(4, "赵六", "小六");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(h1);
        singleLinkedList.add(h2);
        singleLinkedList.add(h3);
        singleLinkedList.add(h4);
        singleLinkedList.detail();
    }

    static class SingleLinkedList {
        //创建头结点
        private HeroNode head = new HeroNode(0, "", "");

        //节点添加方法
        public void add(HeroNode heroNode) {

            //拿到头结点
            HeroNode temp = head;
            //找到最后一个节点,把next域指向要添加的节点
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            temp.next = heroNode;
        }

        //显示链表【遍历】
        public void detail() {
            if (head.next == null) {
                System.out.println("链表为空!");
                return;
            }
            //获取一个临时指针
            HeroNode temp = head.next;
            while (true) {
                if (temp.next == null){
                    System.out.println(temp.toString());
                    System.out.println("就这么多了~~");
                    break;
                }
                System.out.println(temp.toString());
                temp = temp.next;
            }
        }
    }
}

 

运行结果:

 

2、按顺序插入节点

上面的测试是从1,2,3,4依次插入,那么,链表本身是有序的,我们能不能按照no字段乱序插入实现自动递增排序,且从重复元素不再重复插入,

 意思就是,插入顺序改成1432,但链表内部结构依然是1234

 代码只需稍微对add()方法修改一下:

        //按照字段no 升序插入
        public void add2(HeroNode heroNode) {
            //获取指针
            HeroNode temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                } else if (temp.next.no == heroNode.no) {
                    System.out.println("该节点已经存在~");
                    return;
                } else if (temp.next.no > heroNode.no) {
                    break;
                }
                temp = temp.next;
            }
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

 

 这样的插入顺序:

 

 

查看有序的打印结果,依然是1234的顺序,而且重复的元素不再插入: 

 

 

 

其余增删改查查有时间可以做自己思考一下。这里不再赘述。

 

三、单链表新浪、腾讯、百度面试题

 

 

 解答:

1)思路:从头结点的下一个开始,一直遍历,每遍历一个即+1,直到.next为空,此所得即为链表长度

2)依然是遍历,从第一个一直遍历到第length-k的下一个即为k

代码(后补):

3)有点难度,但也是很清晰的。

分为母链和子链,母链双指针,子链单指针

母链拆一个节点拼接到子链头部后第一个,以此类推,得到的全新子链即为反转链:

代码(后补):

 

 

4)同4,反转后,打印即可。

5)以其中一个链表为母链,另一个为子链,遍历子链,挨个插入母联即可。

 

2020-03-29  21:02:13

加载全部内容

相关教程
猜你喜欢
用户评论