数据结构-双向链表的实现

绝地灬酷狼 2022-01-07 04:13 303阅读 0赞

## 题目： ##

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指向原来的header
    183         // 并以新节点作为新的header
    184         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引用赋为null
    227             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         // 将底层数组所有元素赋为null
    253         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     // 倒序toString
    282     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