列表数据结构及使用java实现一个简单的数组列表(ArrayList)和链表(LinkedList)

发表于   |   分类于 左手代码 计算机基础   |   阅读(253)   |   评论(91)

链表，也称为列表，即List

一、链表的结构

1.链表的逻辑结构

链表的逻辑结构

  • 链表的第一个元素叫表名，最后一个元素叫表尾
  • 每个元素有一个指向下一元素地址的指针
2.链表的存储结构

链表的存储结构

  • 每个链表的元素的存储单元未必是连续的空间
3.链表元素的插入

(1)在元素A后面插入元素C

插入元素C

(2)将元素A的下一元素的指针指向元素C，并将元素C的下一个元素的指针指向元素B

修改next的指针

4.链表元素的删除

(0)删除元素F

删除元素C

(1)将删除元素的前一个元素的指向下一元素的指针指向删除元素的下一个元素

修改上一个元素的指向下一个元素的指针

二、单向链表

单向链表

  • 每个元素不仅有存储了本元素指向的数据，还有一个指向下一元素的指针

三、双向链表

双向链表

  • 每个元素不仅有存储了本元素指向的数据，还有一个指向上一元素的指针，一个指向下一元素的指针

四、循环链表

循环链表

  • 相对于单(双)向链表，循环链表的表尾指向了表头，整个链表形成了一个循环

五、通过java实现简单的链表

1.基于数组实现的数组列表ArrayList

自定义实现一个可扩容的动态数组

  1. package com.shixinke.demo.dataStruct;
  4. public class MyArrayList<E> {
  5.     /**
  6.      * 存储的真实的元素个数
  7.      */
  8.     private int size;
  9.     /**
  10.      * 存储的元素值集合
  11.      */
  12.     private E[] data;
  14.     /**
  15.      * 默认的列表容量
  16.      */
  17.     private static final int DEFAULT_CAPACITY = 10;
  19.     public MyArrayList() {
  20.         clearList(DEFAULT_CAPACITY);
  21.     }
  23.     public MyArrayList(int capacity) {
  24.         clearList(capacity);
  25.     }
  27.     /**
  28.      * 清空列表
  29.      */
  30.     public void clear() {
  31.         clearList(DEFAULT_CAPACITY);
  32.     }
  34.     private void clearList(int capacity) {
  35.         this.size = 0;
  36.         if (capacity < 0) {
  37.             capacity = DEFAULT_CAPACITY;
  38.         }
  39.         ensureCapacity(capacity);
  40.     }
  42.     /**
  43.      * 获取数据长度
  44.      * @return
  45.      */
  46.     public int size() {
  47.         return this.size;
  48.     }
  50.     /**
  51.      * 是否为空链表
  52.      * @return
  53.      */
  54.     public boolean isEmpty() {
  55.         return this.size == 0;
  56.     }
  58.     /**
  59.      * 设置值
  60.      * @param index　索引值
  61.      * @param value　设置的值
  62.      */
  63.     public void set(int index, E value) {
  64.         if (index > this.data.length) {
  65.             throw new ArrayIndexOutOfBoundsException();
  66.         }
  67.         this.data[index] = value;
  68.     }
  70.     /**
  71.      * 获取值
  72.      * @param index　索引值
  73.      * @return
  74.      */
  75.     public E get(int index) {
  76.         if (index > this.data.length) {
  77.             throw new ArrayIndexOutOfBoundsException();
  78.         }
  79.         return this.data[index];
  80.     }
  82.     public void add(E value) {
  83.         add(this.size(), value);
  84.     }
  86.     /**
  87.      * 添加元素
  88.      * @param index
  89.      * @param value
  90.      */
  91.     public void add(int index, E value) {
  92.         //1.如果没有剩余的空间，则扩容
  93.         if (this.size == this.data.length) {
  94.             ensureCapacity(this.size* 2 + 1);
  95.         }
  96.         //2.插入位置的后面的元素依次向后移动(从最后的一个元素开始移动，因为插入后，最后一个元素的位置从size-1到了size)
  97.         for (int i = this.size; i > index; i --) {
  98.             this.data[i] = this.data[i-1];
  99.         }
  100.         //3.设置插入元素的值
  101.         this.data[index] = value;
  102.         //4.增加元素个数
  103.         this.size ++;
  104.     }
  106.     /**
  107.      * 删除元素
  108.      * @param index
  109.      * @return
  110.      */
  111.     public E remove(int index) {
  112.         //1.判断索引值是否超过存储的长度
  113.         if (index > this.size) {
  114.             throw new ArrayIndexOutOfBoundsException();
  115.         }
  116.         //2.获取要删除的元素的值
  117.         E oldData = this.data[index];
  118.         //3.删除的元素后面的元素依次向前移动
  119.         for (int i = index; i < this.size; i++) {
  120.             this.data[i] = this.data[i + 1];
  121.         }
  122.         //4.减少元素个数
  123.         this.size --;
  124.         return oldData;
  125.     }
  127.     /**
  128.      * 是否包含某个元素
  129.      * @param value
  130.      * @return
  131.      */
  132.     public boolean contains(E value) {
  133.         for (E e : this.data) {
  134.             if (value.equals(e)) {
  135.                 return true;
  136.             }
  137.         }
  138.         return false;
  139.     }
  141.     /**
  142.      * 返回某个数值的索引值
  143.      * @param value
  144.      * @return
  145.      */
  146.     public int indexOf(E value) {
  147.         for (int i = 0; i < this.data.length; i++) {
  148.             if (value.equals(this.data[i])) {
  149.                 return i;
  150.             }
  151.         }
  152.         return -1;
  153.     }
  155.     public void print() {
  156.         System.out.println();
  157.         for (int i = 0; i < this.size; i++) {
  158.             System.out.println(this.data[i]);
  159.         }
  160.         System.out.println();
  161.     }
  163.     /**
  164.      * 列表扩容
  165.      * @param capacity
  166.      */
  167.     public void ensureCapacity(int capacity) {
  168.         if (capacity < this.size) {
  169.             return;
  170.         }
  171.         E[] oldData = data;
  172.         this.data = (E[]) new Object[capacity];
  173.         for (int i = 0; i < this.size; i++) {
  174.             this.data[i] = oldData[i];
  175.         }
  176.     }
  178. }

注：

(1) 列表的属性：
  • size : 列表元素的个数
  • data : 列表元素的值
(2)添加元素(插入元素)
  • 第一步：判断当前是否有剩余空间(当元素个数和存储的空间一致时，即size == data.length)，如果没有剩余空间，也采用二倍的长度进行扩容
  • 第二步：将插入的位置后面的所有元素都往后移动
  • 第三步：设置插入的元素的值
  • 第四步：增加元素的个数
(3)删除元素
  • 第1步.判断索引值是否超过存储的长度
  • 第2步.获取要删除的元素的值
  • 第3步.删除的元素后面的元素依次向前移动
  • 第4步.减少元素个数
(4)测试
  1. public class MyArrayListTest {
  2.     public static void main(String[] args) {
  3.         MyArrayList<Integer> arrayList = new MyArrayList<Integer>(5);
  4.         arrayList.add(11);
  5.         arrayList.add(12);
  6.         arrayList.add(13);
  7.         arrayList.print();
  8.         arrayList.add(1, 20);
  9.         arrayList.print();
  10.         arrayList.add(3, 35);
  11.         arrayList.add(100);
  12.         arrayList.print();
  13.         System.out.println(arrayList.contains(10));     //false
  14.         System.out.println(arrayList.contains(100));    //true
  15.         System.out.println(arrayList.indexOf(13));      //4
  17.         arrayList.set(5, 50);
  18.         System.out.println(arrayList.get(5));           //50
  19.         arrayList.remove(4);
  20.         arrayList.print();
  22.         arrayList.clear();
  23.         arrayList.print();
  24.         System.out.println(arrayList.isEmpty());        //true
  25.     }
  26. }
2.基于双向链表实现的链表LinkedList
(1)双向链表添加(插入)元素的思路

双向链接添加元素的思路:步骤1

双向链接添加元素的思路:步骤2

双向链接添加元素的思路:步骤3

  • 将插入的元素的前一个元素指针指向原位置元素的前一个元素，将插入元素的后一个元素指针指向原位置所在的元素
  • 原位置元素的前一个元素的后一个元素指针指向新插入的元素，原位置元素的前一个元素的指针指向插入的元素
(2)双向链表添加和删除元素的核心是查找元素(根据索引查找到元素，即原位置的元素)

查找位置元素的方法

  • 第一种方法：从表头开始遍历，从前往后依次到index元素，共遍历index次，当index较大时(在中间坐标的后面)，遍历的次数较多
  • 第二种方法：从表尾开始遍历，从后往前依次到index元素，共遍历size - index次，当index值较小时(从中间坐标的前面)，遍历的次数较多
  • 第三种方法：先计算出中间坐标，判断查找的位置是在中间位置的左边，还是右边，再选择是从开始遍历，还是从结尾遍历，它综合了第一种和第二种方法的优点　
(3)通过java来实现自定义的LinkedList
  1. package com.shixinke.demo.dataStruct;
  3. public class MyLinkedList<E> {
  5.     /**
  6.      * 节点数
  7.      */
  8.     private int size;
  9.     /**
  10.      * 开始节点
  11.      */
  12.     private Node<E> beginNode;
  13.     /**
  14.      * 结束节点
  15.      */
  16.     private Node<E> endNode;
  18.     public MyLinkedList() {
  19.         clearList();
  20.     }
  22.     /**
  23.      * 清空列表
  24.      */
  25.     public void clear() {
  26.         clearList();
  27.     }
  29.     public void clearList() {
  30.         beginNode = new Node<E>(null, null, null);
  31.         endNode = new Node<E>(null, beginNode, null);
  32.         this.size = 0;
  33.     }
  35.     public int size() {
  36.         return this.size;
  37.     }
  39.     public boolean isEmpty() {
  40.         return this.size == 0;
  41.     }
  43.     /**
  44.      * 默认添加到最后
  45.      * @param value
  46.      */
  47.     public void add(E value) {
  48.         add(size(), value);
  49.     }
  51.     public void add(int index, E value) {
  52.         Node<E> node = getNode(index);
  53.         addBefore(node, value);
  54.     }
  56.     public E remove(int index) {
  57.         Node<E> node = getNode(index);
  58.         return remove(node);
  59.     }
  61.     public void set(int index, E value) {
  62.         if (index > this.size) {
  63.             throw new IndexOutOfBoundsException();
  64.         }
  65.         Node<E> node = getNode(index);
  66.         node.data = value;
  67.     }
  69.     public E get(int index) {
  70.         if (index > this.size) {
  71.             throw new IndexOutOfBoundsException();
  72.         }
  73.         Node<E> node = getNode(index);
  74.         return node.data;
  75.     }
  77.     public boolean contains(E value) {
  78.         Node<E> node = beginNode;
  79.         for (int  i= 0; i < size; i++) {
  80.             if (value.equals(node.data)) {
  81.                 return true;
  82.             }
  83.             node = node.next;
  84.         }
  85.         return false;
  86.     }
  88.     public int indexOf(E value) {
  89.         Node<E> node = beginNode;
  90.         for (int  i= 0; i < size; i++) {
  91.             if (value.equals(node.data)) {
  92.                 return i;
  93.             }
  94.             node = node.next;
  95.         }
  96.         return -1;
  97.     }
  99.     private Node<E> getNode(int index) {
  100.         return getNode(index, 0, size() );
  101.     }
  104.     /**
  105.      * 通过索引获取节点
  106.      * @param index　节点索引
  107.      * @param min　　　起始位置
  108.      * @param max　　　结束位置
  109.      * @return
  110.      */
  111.     private Node<E> getNode(int index, int min, int max) {
  112.         Node<E> p;
  113.         if (index > max || index < min) {
  114.             throw new IndexOutOfBoundsException();
  115.         }
  116.         /**
  117.          * 类似于对半查找
  118.          */
  119.         int half = this.size() / 2;
  120.         if (index < half) {
  121.             /**
  122.              * 1.索引值在前半部分(总共只有size个元素)，则搜索的元素从开始元素开始往后，最后面的元素即为要查找的元素
  123.              */
  124.             p = beginNode;
  125.             for (int i = 0; i < index; i++) {
  126.                 p = p.next;
  127.             }
  128.         } else {
  129.             /**
  130.              * 索引值在后半部分，则搜索的元素从结束元素开始往前，最前面的一个元素即是要查找的元素
  131.              */
  132.             p = endNode;
  133.             for (int i = size(); i > index; i --) {
  134.                 p = p.prev;
  135.             }
  136.         }
  138.         return p;
  139.     }
  141.     private E remove(Node<E> node) {
  142.         E oldData = node.data;
  143.         //1.修改删除元素的前一个元素的next指针的指向，指向删除元素的下一个元素
  144.         node.prev.next = node.next;
  145.         //2.修改删除元素的下一个元素的prev指针的指向，指向删除元素的前一个元素
  146.         node.next.prev = node.prev;
  147.         //3.减少元素个数
  148.         this.size -- ;
  149.         //4.要删除节点本身的资源释放
  150.         node.next = null
  151.         node.prev = null 
  152.         node.data = null
  153.         return oldData;
  154.     }
  156.     /**
  157.      * 从某个元素前面插入元素(因为新插入的元素，要占用原来元素的位置，所以是在原元素前面插入)
  158.      * @param node
  159.      * @param value
  160.      */
  161.     private void addBefore(Node<E> node, E value) {
  162.         //1.生成新节点，它的值为value,它的prev指针为当前节点的前一个元素，它的next指针为当前元素
  163.         Node<E> newNode = new Node<E>(value, node.prev, node);
  164.         //2.修改当前节点的前一个元素的next指针，指向新插入的元素
  165.         node.prev.next = newNode;
  166.         //3.修改当前元素的prev指针，指向当前元素
  167.         node.prev = newNode;
  168.         //4.增加元素个数
  169.         this.size ++;
  170.     }
  172.     public void print() {
  173.         System.out.println();
  174.         Node<E> node = beginNode;
  175.         for (int i = 0; i< this.size; i++) {
  176.             node = node.next;
  177.             System.out.println(node.data);
  178.         }
  179.         System.out.println();
  180.     }
  182.     /**
  183.      * 元素节点
  184.      * @param <E>
  185.      */
  186.     private class Node<E> {
  187.         /**
  188.          * 存储的数据
  189.          */
  190.         private E data;
  191.         /**
  192.          * 前一个节点指针
  193.          */
  194.         private Node<E> prev;
  195.         /**
  196.          * 后一节点指针
  197.          */
  198.         private Node<E> next;
  200.         public Node(E value, Node<E> p, Node<E> n) {
  201.             this.data = value;
  202.             this.prev = p;
  203.             this.next = n;
  204.         }
  205.     }
  206. }

插入节点：

  • 第１步：通过index获取插入的位置的原节点元素
  • 第２步.生成新节点，它的值为value,它的prev指针为当前节点的前一个元素，它的next指针为当前元素
  • 第3步.修改当前节点的前一个元素的next指针，指向新插入的元素
  • 第4步.修改当前元素的prev指针，指向当前元素
  • 第5步.增加元素个数

删除节点：

  • 第１步：通过index获取插入的位置的原节点元素
  • 第2步.修改删除元素的前一个元素的next指针的指向，指向删除元素的下一个元素
  • 第3步.修改删除元素的下一个元素的prev指针的指向，指向删除元素的前一个元素
  • 第4步.减少元素个数
(4)测试功能代码
  1. package com.shixinke.demo.dataStruct;
  3. public class MyLinkedListTest {
  5.     public static void main(String[] args) {
  6.         MyLinkedList<String> linkedList = new MyLinkedList<String>();
  7.         linkedList.add("红1");
  8.         linkedList.print();
  9.         linkedList.add("蓝2");
  10.         linkedList.print();
  11.         linkedList.add("白3");
  12.         linkedList.add("黄4");
  13.         linkedList.add("绿5");
  14.         linkedList.add("黑6");
  15.         linkedList.print();
  16.         System.out.println(linkedList.size());                //6
  17.         System.out.println(linkedList.contains("紫7"));        //false
  18.         System.out.println(linkedList.contains("绿5"));        //true
  19.         System.out.println(linkedList.indexOf("黄4"));         //4
  20.         System.out.println(linkedList.indexOf("青8"));         //-1
  23.         linkedList.clear();
  24.         System.out.println(linkedList.isEmpty());              //true
  25.     }
  26. }

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开