数据结构-链表-Java实现

ゝ一世哀愁。 2023-10-04 17:06 42阅读 0赞

### Java实现链表数据结构 ###

链表又可以分为单向链表、双向链表、环形链表

#### 一、单向链表 ####

在单向链表中，第一个节点是链表头指针，指向最后一个节点的指针设为None，表示它是链表尾，不指向任何地方

##### 建立链表 #####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]

首先需要定义一个类，该类就是链表上的各节点，类中有一个属性为链表下一指针，指向下一个节点，默认为null

class Node {
        
        private int num = 0;
        private Node next = null;
    }

完成之后就是链表的设计，首先需要指定链表头，可以实例一个对象，然后指定next的元素，随后逐渐将next后移，即是将next赋值为下一个元素

链表可以由数组创建而来，总之来源根据需求自定义，下面以列表为例

public Node createNode(){
        
    
            // 新建一个列表，用于存放数组
            ArrayList<Integer> datas = new ArrayList<Integer>();
            datas.add(1);
            datas.add(2);
            datas.add(3);
    
            // 链表的头
            Node head = new Node();
            // 初始化链表头，如果在Node类中已经初始化完成了， 这步可以省略，也可以按照需要判断是否需要这一步
            head.setNum(0);
            head.setNext(null);
    
        	// 这个Node节点是尾指针
            Node ptr = head;
    
            int i = 0;
    
            while (i < datas.size()) {
        
    
                // 下一个链表节点
                Node newNode = new Node();
                newNode.setNum((Integer) datas.get(i));
                ptr.setNext(newNode);
                // 上述的代码，可以在Node类中的构造器中传入参数，这里就使用空参构造器了
    
                // 指针后移
                ptr = newNode;
    
                i ++ ;
            }
    
            return head;
        }

##### 遍历链表 #####

遍历的过程就是使用指针运算来访问链表的每个节点，在循环中逐渐将指针后移，实现链表的遍历，这里以单向链表为例

public void getNode(Node head){
        
            Node ptr = head.getNext();
            while (ptr != null){
        
                System.out.println("链表：" + ptr.getNum());
                ptr = ptr.getNext();
            }
        }

#### 二、双向链表 ####

单向链表和环形链表都是属于拥有方向性的链表，只能单向遍历，如果由于某种原因造成了某个连接断裂，那后面的链表数据便会遗失而无法复原。所以，我们可以将两个方向不同的链表结合起来，除了存放数据的字段之外，它还有两个指针变量，除了类似于单向链表的下一个指针next外，还需要一个指针指向上一个数据，这样的链表就是双向链表

<table> 
 <thead> 
  <tr> 
   <th>llink</th> 
   <th>data</th> 
   <th>rlink</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>指向上一个节点</td> 
   <td>节点</td> 
   <td>指向下一个节点</td> 
  </tr> 
 </tbody> 
</table>

建立过程中在Node类中新增一个指向上一个节点的属性即可，在遍历建立的时候为next赋值的同时也为tail赋值即可

class Node {
        private int num = 0;
        private Node rlink = null;
        private Node llink = null;
    }

同理，在遍历的时候也可以进行双向遍历，可以从左向右，也可以从右向左，两者的区别只是遍历的属性为llink还是rlink而已

#### 三、环形链表 ####

环形链表就是将单链表的尾部指向头部，从而形成一个单方向的环形结构，环形链表中每个元素都可以是head，也都可以是尾部，这样就不用担心链表头指针遗失的问题，而且在遍历链表的时候可以在任一节点来遍历其他节点

##### 环形链表的建立 #####

在环形链表的建立过程中，与单向链表相似，只是在链表的最后一个元素的next指向head即可

##### 环形链表的遍历 #####

与单向链表的遍历十分相似，只不过单向链表的结束条件是ptr.next = null,而环形链表的结束条件是ptr.next = head

public void getNode(Node head){
        
            Node ptr = head.getNext();
            while (ptr != null){
        
                System.out.println("链表：" + ptr.getNum());
                ptr = ptr.getNext();
                if(ptr.getNext == head){
        
                	break;
                }
            }
        }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA54mn56CB5paH_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/97062f74ae654475adfa80d4c06f83f3.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54mn56CB5paH,size_20,color_FFFFFF,t_70,g_se,x_16