博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
数据结构-双向链表的实现
阅读量:6111 次
发布时间:2019-06-21

本文共 7539 字,大约阅读时间需要 25 分钟。

题目:

1 双向升序链表结构定义如下: 2 class Node { 3  4         private int value;// 保存节点的数据 5          6         private Node pre, next;// 保存上个节点的引用、指向下一个节点的引用 7 } 8 编程实现对该双向链表的插入、删除操作 9 public Node insert(Node head, int value);//返回头节点10 public void delete(Node head, int value);

双向链表实现

1 package com.ruihai.collection.test;  2   3 /**  4  * 双向升序链表  5  *   6  * 参考Java.util包的LinkedList实现  7  * @author shenruihai.com  8  */  9 public class LinkedList { 10  11     // 定义一个内部类Node,Node实例代表链表的节点 12     private class Node { 13  14         private int value;// 保存节点的数据 15          16         private Node pre;// 保存上个节点的引用 17         18         private Node next; // 指向下一个节点的引用 19  20         // 无参构造器 21         public Node() { 22         } 23  24         // 初始化全部属性的构造器 25         public Node(int value, Node pre, Node next) { 26  27             this.value = value; 28             this.pre = pre; 29             this.next = next; 30  31         } 32     } 33  34     // 保存该链表的头节点 35     private Node header; 36     // 保存该链表的尾节点 37     private Node tail; 38     // 保存该链表中已包含的节点数 39     private int size; 40  41     // 创建空链表 42     public LinkedList() { 43  44         // 空链表,header和tail都是null 45         header = null; 46         tail = null; 47  48     } 49  50     // 以指定数据元素来创建链表,该链表只有一个元素 51     public LinkedList(int element) { 52  53         header = new Node(element, null, null); 54         // 只有一个节点,header、tail都指向该节点 55         tail = header; 56         size++; 57  58     } 59  60     // 返回链表的长度 61     public int length() { 62         return size; 63     } 64  65     // 获取链式线性表中索引为index处的元素 66     public int get(int index) { 67  68         return getNodeByIndex(index).value; 69  70     } 71  72     // 根据索引index获取指定位置的节点 73     public Node getNodeByIndex(int index) { 74  75         if (index < 0 || index > size - 1) { 76             throw new IndexOutOfBoundsException("线性表索引越界"); 77         } 78          79         if (index <= size / 2) { 80  81             // 从header节点开始 82             Node current = header; 83             for (int i = 0; i <= size / 2 && current != null; i++, current = current.next) { 84                 if (i == index) { 85  86                     return current; 87  88                 } 89             } 90  91         } else { 92  93             // 从tail节点开始搜索 94             Node current = tail; 95             for (int i = size - 1; i > size / 2 && current != null; i++, current = current.pre) { 96                 if (i == index) { 97  98                     return current; 99 100                 }101             }102         }103         return null;104     }105 106     // 查找链式线性表中指定元素的索引107     public int locate(int element) {108 109         // 从头结点开始搜索110         Node current = header;111         for (int i = 0; i < size && current != null; i++, current = current.next) {112 113             if (String.valueOf(current.value).equals(element)) {114                 return i;115             }116 117         }118         return -1;119 120     }121 122     // 向线性链表的指定位置插入一个元素123     public void insert(int element, int index) {124 125         if (index < 0 || index > size) {126             throw new IndexOutOfBoundsException("线性表索引越界");127         }128 129         // 如果还是空链表130         if (header == null) {131 132             add(element);133 134         } else {135 136             // 当index为0时,也就是在链表头处插入137             if (index == 0) {138 139                 addAtHeader(element);140 141             } else {142 143                 // 获取插入点的前一个节点144                 Node pre = getNodeByIndex(index - 1);145                 // 获取插入点的节点146                 Node next = pre.next;147                 // 让新节点的next引用指向next节点,pre引用指向pre节点148                 Node newNode = new Node(element, pre, next);149                 // 让pre的next节点指向新节点150                 pre.next = newNode;151                 // 让pre的下一个节点的pre指向新节点152                 next.pre = newNode;153                 size++;154             }155         }156     }157 158     // 采用尾插法为链表添加新节点159     public void add(int element) {160 161         // 如果该链表还是空链表162         if (header == null) {163 164             header = new Node(element, null, null);165             // 只有一个节点,header、tail都指向该节点166             tail = header;167 168         } else {169 170             // 创建新节点,新节点的pre指向原tail节点171             Node newNode = new Node(element, tail, null);172             // 让尾节点的next指向新增的节点173             tail.next = newNode;174             // 以新节点作为新的尾节点175             tail = newNode;176         }177         size++;178     }179 180     // 采用头插法为链表添加新节点181     public void addAtHeader(int element) {182         // 创建新节点,让新节点的next指向原来的header183         // 并以新节点作为新的header184         header = new Node(element, null, header);185         // 如果插入之前是空链表186         if (tail == null) {187 188             tail = header;189 190         }191         size++;192     }193 194     // 删除链式线性表中指定索引处的元素195     public int delete(int index) {196 197         if (index < 0 || index > size - 1) {198 199             throw new IndexOutOfBoundsException("线性表索引越界");200 201         }202         Node del = null;203         // 如果被删除的是header节点204         if (index == 0) {205 206             del = header;207             header = header.next;208             // 释放新的header节点的pre引用209             header.pre = null;210 211         } else {212 213             // 获取删除节点的前一个节点214             Node pre = getNodeByIndex(index - 1);215             // 获取将要被删除的节点216             del = pre.next;217             // 让被删除节点的next指向被删除节点的下一个节点218             pre.next = del.next;219             // 让被删除节点的下一个节点的pre指向pre节点220             if (del.next != null) {221 222                 del.next.pre = pre;223 224             }225 226             // 将被删除节点的pre、next引用赋为null227             del.pre = null;228             del.next = null;229 230         }231         size--;232         return del.value;233     }234 235     // 删除链式线性表中最后一个元素236     public int remove() {237 238         return delete(size - 1);239 240     }241 242     // 判断链式线性表是否为空表243     public boolean empty() {244 245         return size == 0;246 247     }248 249     // 清空线性表250     public void clear() {251 252         // 将底层数组所有元素赋为null253         header = null;254         tail = null;255         size = 0;256 257     }258 259     public String toString() {260 261         // 链表为空链表262         if (empty()) {263 264             return "[]";265 266         } else {267 268             StringBuilder sb = new StringBuilder("[");269             for (Node current = header; current != null; current = current.next) {270                271                 sb.append(String.valueOf(current.value).toString() + ", ");272 273             }274             int length = sb.length();275             return sb.delete(length - 2, length).append("]").toString();276 277         }278 279     }280 281     // 倒序toString282     public String reverseToString() {283 284         if (empty()) {285 286             return "[]";287 288         } else {289 290             StringBuilder sb = new StringBuilder("[");291             for (Node current = tail; current != null; current = current.pre) {292 293                 sb.append(String.valueOf(current.value).toString() + ", ");294 295             }296             int length = sb.length();297             return sb.delete(length - 2, length).append("]").toString();298 299         }300 301     }302     303 }

小记:这是今天下午朋友发给我的一道面试题,看到的时候想:“这不就是考的双向链表嘛,链表这部分我还是很清楚的”,但是通过代码去实现的时候才发现双向链表通过代码实现还是比较麻烦的,最后参考LinkedList的源码,写了这段代码。

转载于:https://www.cnblogs.com/juihai/p/10544639.html

你可能感兴趣的文章
Django之FBV与CBV
查看>>
Vue之项目搭建
查看>>
app内部H5测试点总结
查看>>
Docker - 创建支持SSH服务的容器镜像
查看>>
[TC13761]Mutalisk
查看>>
三级菜单
查看>>
Data Wrangling文摘:Non-tidy-data
查看>>
加解密算法、消息摘要、消息认证技术、数字签名与公钥证书
查看>>
while()
查看>>
常用限制input的方法
查看>>
Ext Js简单事件处理和对象作用域
查看>>
IIS7下使用urlrewriter.dll配置
查看>>
12.通过微信小程序端访问企查查(采集工商信息)
查看>>
WinXp 开机登录密码
查看>>
POJ 1001 Exponentiation
查看>>
HDU 4377 Sub Sequence[串构造]
查看>>
云时代架构阅读笔记之四
查看>>
WEB请求处理一:浏览器请求发起处理
查看>>
Lua学习笔记(8): 元表
查看>>
PHP经典算法题
查看>>