欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构02-链表

程序员文章站 2023-10-31 21:39:22
说明:由于该数据结构是由java并且是原生实现,所以与C有一些出入,不过原理是相同的 1.链表的定义 为了表示线性表元素a与a+1的逻辑关系,存储数据时,除了存储元素本身的信息之外,还存储了直接后继元素的位置信息。这两部分组成的数据元素被称为“结点”,一个结点分为两部分,存放数据元素信息的部分被称为 ......

说明:由于该数据结构是由java并且是原生实现,所以与c有一些出入,不过原理是相同的

1.链表的定义

    为了表示线性表元素a与a+1的逻辑关系,存储数据时,除了存储元素本身的信息之外,还存储了直接后继元素的位置信息。这两部分组成的数据元素被称为“结点”,一个结点分为两部分,存放数据元素信息的部分被称为数据域,

    存放直接后继元素位置的部分被称为指针域。

    单链表:结点指针域只存放直接后继元素位置的链表,也叫单向链表。

    双链表:结点指针域同时存放前驱元素和后继元素位置的链表,也叫双向链表。

    循环链表:一般的链表尾结点(最后一个结点)的指针域一般null,但是有的链表将最后一个节点的指针域指向头结点,构成一个环,称作循环链表。

    头结点: 一个链表的头节点,就是指针域指向该链表的第一个结点的结点,一般用来唯一确定一个链表(也有的链表是不带头结点的,那时我们通过链表的第一个结点来确定链表),注意:头结点的数据与是null

2.实现原理

    链表的每一个结点包括两部分,数据域和指针域,数据域用来存储数据,指针域用来存储后继结点的位置。

 1 class link<t>{
 2     /**
 3     *用来存储数据
 4     */
 5     t data;
 6     /**
 7     *用来存储下一结点位置
 8      */
 9     link next;
10 }

3.链表的基本操作

    1.初始化 init() 创建一个链表

    2.清空 clear() 清空一个链表

    3.销毁 destroy() 销毁链表

    4.在头部插入一个结点 insertfront()

    5.在尾部插入一个结点 insertbackend()

    6.在任意位置插入一个结点 insertindex()

    7.删除任意位置元素 delete()

    8.查找元素 find()

    9.获取指定位置节点的值 get()

4.代码实现

  4.1链表代码实现

  1 package com.xiaobai.linelist;
  2 
  3 /**
  4  * @author: xiaobai
  5  * @date: 2019/5/1 9:00
  6  * @email:
  7  * @address:
  8  * @desc 模拟单链表操作
  9  * @version 1.0
 10  */
 11 @suppresswarnings("all")
 12 public final class link<t> {
 13     /**
 14      * data 是要存储的数据
 15      */
 16     private t data;
 17     /**
 18      * next是下一结点的引用位置
 19      */
 20     public link<t> next;
 21 
 22     /**
 23      * 初始化操作 构造方法返回一个空结点
 24      */
 25     public link(){
 26         this.next = null;
 27         this.data = null;
 28     }
 29 
 30     /**
 31      * 构造一个新的链表结点
 32      * 新结点是没有后继结点的 所以直接null
 33      * @param data 数据
 34      */
 35     public link(t data){
 36         this.data = data;
 37         this.next = null;
 38     }
 39 
 40     /**
 41      * 清空链表操作
 42      * @param link 要被清空的链表头节点
 43      */
 44     public void clear(){
 45         //让每一个结点的引用都为 null gc 自动回收
 46         link<t> link = this;
 47         while(link.next!=null){
 48             link curr = link.next;
 49             link.next = link.next.next;
 50             curr = null;
 51         }
 52         link = null;
 53     }
 54 
 55     /**
 56      * 销毁链表 这里的销毁和清空我认为没有什么区别,所以直接调用
 57      * 如果大家认为有区别的话,可以与我交流
 58      * @param link 被销毁的链表
 59      */
 60     public void destroy(){
 61         this.clear();
 62     }
 63 
 64     /**
 65      * 在链表的头部插入一个结点(默认是带头结点的链表)
 66      * @param head 链表的头节点
 67      * @param data 被插入的数据
 68      * @return 插入结果
 69      */
 70     public boolean insertfront(t data){
 71         //先构建一个新的结点
 72         link<t> node = new link<t>(data);
 73         try {
 74             //将结点插入到头部 即 新节点后继指向原来的第一个结点  头节点后继指向新节点
 75             node.next = this.next;
 76             this.next = node;
 77             return true;
 78         }catch (exception e){
 79             e.printstacktrace();
 80             return false;
 81         }
 82     }
 83 
 84     /**
 85      * 在链表的尾部插入一个结点
 86      * @param head 链表头节点
 87      * @param data 要插入的数据
 88      * @return 插入结果
 89      */
 90     public boolean insertbackend(t data){
 91         //先构建一个新的结点
 92         try {
 93             link<t> node = new link<t>(data);
 94             //然后找到链表的尾
 95             link<t> point = this.next;
 96             while(point.next!=null){
 97                 point = point.next;
 98             }
 99             //插入
100             point.next = node;
101             return true;
102         } catch (exception e) {
103             e.printstacktrace();
104             return false;
105         }
106     }
107 
108     /**
109      * 在任意位置插入一个结点
110      * @param head 要插入的链表
111      * @param i  插入位置 从0开始
112      * @param data 插入的数据
113      * @return 插入结果
114      */
115     public boolean insertindex(int i,t data){
116         link curr = this.next;
117         //空链表 拒绝插入
118         if(null == curr && i > 0){
119             return false;
120         }
121         int count = 0;
122         //找到被插入的位置(要找被插入位置前一个)
123         while(count != i-1 && null != curr){
124             curr = curr.next;
125             count ++;
126         }
127         //如果循环提前结束 说明i值过大
128         if(count != i-1){
129             return false;
130         }
131         //开始插入节点
132         link<t> node = new link<t>(data);
133         node.next = curr.next;
134         curr.next = node;
135         return true;
136     }
137 
138     /**
139      * 删除任意位置元素
140      * @param i 被删除的位置  从0 开始
141      * @return 被删除的元素 删除失败返回null
142      */
143     public t delete(int i){
144         t del = null;
145         int count = 0;
146         link<t> curr = this.next;
147         //找到被删除结点的前一个结点
148         while (curr != null&& count < i-1){
149             curr = curr.next;
150             count++;
151         }
152         //如果不满足条件 删除失败
153         if(count!=i-1){
154             return del;
155         }
156         //如果找到 执行删除操作 (gc 自动释放)
157         del = curr.next.data;
158         curr.next = curr.next.next;
159         return del;
160     }
161 
162     /**
163      * 查找元素是否存在  可能需要重写存储对象的equals方法
164      * @param data 被查找元素
165      * @return 查找结果
166      */
167     public boolean find(t data){
168         link curr = this.next;
169         while(curr != null){
170             if(curr.data.equals(data)||curr.data ==data){
171                 return true;
172             }
173             curr = curr.next;
174         }
175         return false;
176     }
177 
178     /**
179      * 获取指定位置的元素
180      * @param i 位置
181      * @return 获取到的值 没有返回null
182      */
183     public t get(int i) {
184         t data = null;
185         link<t> curr = this.next;
186         int count = 0;
187         while(count!=i && curr!=null){
188             curr = curr.next;
189             count ++;
190         }
191         if(count == i && curr!= null){
192             data = curr.data;
193         }
194         return data;
195     }
196 
197     @override
198     public string tostring() {
199         stringbuilder sb = new stringbuilder().append("hashcode = "+this.hashcode()).append(" {head -> ");
200         link<t> curr = this.next;
201         while (curr!=null){
202             sb.append(curr.data+" -> ");
203             curr = curr.next;
204         }
205         sb.append(" null}");
206         return sb.tostring();
207     }
208 }

 

  4.2  测试代码及结果

 1 /**
 2  * @author: xiaobai
 3  * @date: 2019/5/1 9:42
 4  * @email: 
 5  * @address:
 6  * @version 1.0
 7  */
 8 public class testlink {
 9     public static void main(string[] args) {
10         system.out.println("初始化链表");
11         link<integer> link = new link<>();
12         system.out.println("当前链表: "+link);
13 
14         system.out.println("在前端插入一个元素 5");
15         link.insertfront(5);
16         system.out.println("当前链表: "+link);
17 
18         for(int i=1;i<=10;i++){
19             link.insertbackend(i);
20         }
21         system.out.println("依次从后端继续插入10个数后: "+link);
22 
23         link.insertindex(3,100);
24         //索引从0开始
25         system.out.println("在第三个位置上插入100以后的链表 "+link);
26 
27         system.out.println("在第100个位置上插入0 "+link.insertindex(100,0));
28 
29         system.out.println("删除第三个位置上的元素"+link.delete(3));
30         system.out.println(link);
31 
32         system.out.println("查找元素10的结果"+link.find(10));
33         system.out.println("查找元素100的结果"+link.find(100));
34 
35         system.out.println("获取第3个结点的值 "+link.get(3));
36         system.out.println("获取第999个结点的值 "+link.get(999));
37 
38         link.clear();
39         system.out.println("执行清空操作后的链表: "+link);
40 
41         link.destroy();
42 
43     }
44 }

      运行结果图:

数据结构02-链表