说到集合框架就要聊聊数据结构了,集合框架内部是有数据结构的。使用集合框架则是对数据进行增删改查的操作。
常见的数据结构有 数组 、动态数组、 链表、 队列、 堆栈、 树、 二叉树、 图
一、 数组数据结构
数组是一片连续的数据空间
数组内存空间是连续的,内存地址指向的是数组中第一个数的内存地址。
注:数组长度一旦声明是无法改变的,且char数组可以直接输出来。
由于数组底层是封装了指针的,所以数组的查询操作非常快。
二、动态数组
动态数组,顾名思义,长度是可变的。java中具体实现的类是ArrayList类
实现原理如图:
增加:创建一个新的数组,长度为原数组长度+1。先将原数组中所有的数拷贝到新数组,然后将要添加的数据加入到新数组的最后一位,最后将原数组指向新数组
删除:创建一个长度为原数组长度-1的新数组。将指定要删除的数之前所有的数全部拷贝到新数组中,将在这个数之后的所有数继续向新数组里拷贝。
三、链表
链表又分单向链表,双向链表,环形链表
以单链表为例:
每个节点里面都放两个数据,一个用来存数据的,一个用来存下一个节点的地址的。这样就组成了一个链式结构。
增加:先将key指向插入位置原来的元素,然后将前一个节点的key指向要插入的元素,最后将前一个节点的key指向空。
删除:先将要删除节点的前一个节点指向后一个节点,然后先将前一个节点的key指向null 最后将要删除的节点的key指向null
链式结构代码如下:
public class MyLinkedList { Node head = null;//头节点 Node last = null;//尾节点 int count = 0;//记录下标 //增加数据 public void add(String s) { Node n = new Node(s); if(head == null) { head = n; last = n; }else { last.next = n; last=n; } count++; } //在指定位置插入数据 public void add(int index,String s) { int num = 0; Node node = new Node(s); Node n = head; while(num<index-1) { n=n.next; num++; } node.next = n.next; n.next = node; count++; } //根据下标获取数据 public String get(int index) { Node n = getNodeByIndex(index); return n.data; } //获取长度 public int size() { return count; } public void remove(String s) { for(int i = 0;i<size();i++) { if(getNodeByIndex(i).data.equals(s)) { remove(i); } } } //根据下标修改数据 public void set(int index , String s) { Node n1 = getNodeByIndex(index-1); Node n = new Node(s); Node n2 = getNodeByIndex(index); n1.next=n; n.next=n2.next; n2.next=null; } //根据下标移除数据 public void remove(int index) { int num = 0; Node n = head; if(head!=null){ if(index != 0 ) { while(num < index-1) { n = n.next; num++; } Node m =n.next; if(n.next!=last) { n.next = m.next; m.next = null; }else if(n.next == last){ n.next = null; } }else if(index == 0){ head = head.next; n.next=null; } count--; } } //获取节点 private Node getNodeByIndex(int index) { int num = 0; Node n = head; while(num<index) { n=n.next; num++; } if(n!=null) { return n; } return null; } //节点类 private class Node{ String data; Node next; Node (String data){ this.data=data; } @Override public String toString() { // TODO Auto-generated method stub return data; } } }