数据结构--链表实现【JAVA】

微信公众号同步更新

欢迎和小白一起成长，985计算机硕士，有任何学习，保研等问题都可以公众号私信留言哦！

微信搜索：三喂树屋

1.链表定义

物理上非连续，非顺序的数据结构，由若干节点组成

2. 分类

单向链表:每一个节点包含：一个存放数据的变量data，一个指向下一个节点的指针next。
双向链表:双向链表比单向链表多了一个指向前置节点的prev指针。

3. 存储结构：

数组是顺序存储，链表则是随机存储。对比图如下

4. 单链表基本操作

4.1 查找节点

查找需要从头节点开始，如果查找第三个节点，需要以此访问前两个节点，例图如下：

4.2 更新节点

首先查找到要更新的节点，直接更新data即可

4.3 插入节点

插入节点分为三种：尾部插入，头部插入，中间插入

4.3.1 尾部插入

尾部插入是最简单的，将最后一个节点的next指向新的插入的节点即可

4.3.2 头部插入

头部插入分为两步，首先将新节点的next指向头节点，然后将新节点变成头节点(Head指向新节点)

4.3.3 中间插入

中间插入也分为两步，将新节点的next指向插入位置的节点，然后嵌入位置的前置节点的next指向新节点。

4.4 删除节点

删除节点也分为三种情况，尾部删除，头部删除，中间删除

4.4.1 尾部删除

尾部删除是最简单的，将倒数第二个节点的next指向null即可

4.4.2 头部删除

将头节点指向下一个元素即可

4.4.3 中间删除

中间删除将删除节点的前置节点的next指向要删除元素的后一个节点即可

5. 代码实现

5.1 首先准备个Node类，即为存储data和next的节点

classNode{publicint data;publicNode next;publicNode(int data){this.data= data;}}

5.2 完整代码如下，看注释即可

publicclassLinkedListTest{privateNode head=null;privateNode last=null;privateint size=0;publicNodeget(int index)throwsException{//判断溢出if(index<0||index>=this.size){thrownewException("超过链表范围");}Node p= head;//查找节点位置for(int i=0;i<index;i++){
            p= p.next;}return p;}publicvoidinsert(int index,int element)throwsException{if(index<0||index>this.size){thrownewException("超过链表节点范围");}Node node=newNode(element);//头部插入if(index==0){
            node.next= head;
            head= node;}//尾部插入elseif(index==this.size){
            last.next= node;
            last= node;}else{//中间插入Node prevNode=get(index-1);
            node.next= prevNode.next;
            prevNode.next= node;}this.size++;}publicNoderemove(int index)throwsException{if(index<0||index>=this.size){thrownewException("超过链表节点范围");}Node removeNode=null;//头部删除if(index==0){
            removeNode=this.head;this.head= removeNode.next;}elseif(index==this.size-1){//尾部删除Node prevNode=get(index-1);
            removeNode= prevNode.next;
            prevNode.next=null;
            last.next= prevNode;}else{//中间删除Node prevNode=get(index-1);
            removeNode= prevNode.next;
            prevNode.next= prevNode.next.next;}this.size--;return removeNode;}//打印元素的函数publicvoidprint(){Node p= head;while(null!=p){System.out.println(p.data);
            p= p.next;}}

5.3 测试程序如下：

publicstaticvoidmain(String[] args)throwsException{LinkedListTest linkedList=newLinkedListTest();
        linkedList.insert(0,1);
        linkedList.insert(0,2);
        linkedList.insert(0,3);
        linkedList.remove(1);
        linkedList.print();}