一、集合框架接口图
在开始实现LinkedList类和ArrayList 类之前，首先我们来认识一下Java集合框架的接口图。
说明：
- Java的集合类主要由两个接口开始衍生，即Collection和Map，它们是Java集合框架的根接口。
- Collection是一个高度抽象出来的集合，它包含了List和Set两大分支。
- LIst是一个有序的队列，它的实现类有LinkedList，ArrayList，Vector，Stack；
Set是一个不允许有重复元素的集合。它的实现类有HastSet,TreeSet。 - ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法。
二、实现LinkedList
1.LinkedList定义
LinkedList是一个双向链表,建议在有频繁插入和删除时使用。
LinkedList不是线程安全的。
2.LinkedList方法
通过查阅jdk文档，我们可以看到它的方法。下面列举一二。
3.实现MyLinkedList
class ListNodeX{
public int data;
public ListNodeX prev;
public ListNodeX next;
public ListNodeX(int data){
this.data = data;
}
}
public class MyLinkedList2 {
public ListNodeX head;//头结点
public ListNodeX last;//尾结点
//头插法
public void addFirst(int data) {
ListNodeX node = new ListNodeX(data);
if(head == null){
this.head = node;
}else{
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//尾插法
public void addLast(int data) {
ListNodeX node = new ListNodeX(data);
if(head == null){
this.head = node;
this.last = node;
}else{
this.last.next = node;
node.prev = this.last;
this.last = node;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {
ListNodeX cur = this.head;
if(index < 0||index > size())return;//判断合法性
if(index == 0){
addFirst(data);//头插
return;
}
if(index==size()){
addLast(data);//尾插
return;
}
while(index != 0){
cur = cur.next;
index--;
}
ListNodeX node = new ListNodeX(data);
//双链表的插入需要四步，顺序可以调换
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;//不要写漏.prev
cur.prev = node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNodeX cur = head;
while(cur!=null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
ListNodeX cur = this.head;
while(cur!=null){
if(cur.data == key){
if(cur==this.head){//为头结点
this.head = this.head.next;//head后移
if(this.head==null){//后移后的头结点为空
this.last = null;//将尾结点置空
}else{
this.head.prev = null;//不为空，将前驱结点置空
}
}else{//不为头结点
cur.prev.next = cur.next;
if(cur.next == null){//为尾结点
this.last = cur.prev;
}else{//不为尾结点
cur.next.prev = cur.prev;
}
}
return;
}else{
cur = cur.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key) {
ListNodeX cur = this.head;
while(cur!=null){
if(cur.data == key){
if(cur==this.head){//为头结点
this.head = this.head.next;
if(this.head==null){
this.last = null;
}else{
this.head.prev = null;
}
}else{
cur.prev.next = cur.next;
if(cur.next == null){//为尾结点
this.last = cur.prev;
}else{
cur.next.prev = cur.prev;
}
}
cur = cur.next;//与只删除第一次出现的代码几乎相同，只多了继续后移的这句代码
}else{
cur = cur.next;
}
}
}
//得到链表的长度
public int size() {
int count = 0;
ListNodeX cur = head;
while(cur!=null){
count++;
cur = cur.next;
}
return count;
}
public void display() {
ListNodeX cur = head;
while(cur!=null){
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
public void clear() {
ListNodeX cur = this.head;
while(cur!=null){
ListNodeX curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
this.head = null;
this.last = null;
}
}
三、实现ArrayList
1.ArrayList定义
ArrayList的底层结构通过数组实现。
2.ArrayList方法
3.实现MyArrayList
public class MyArrayList {
public int[] elem;
public int usedSize;
public static final int intCapacity = 10;
public MyArrayList(){
this.elem = new int[intCapacity];
this.usedSize = 0;
}
public boolean isFull(){
if(usedSize == this.elem.length){
return true;
}
return false;
}
//增加元素
public void add(int pos,int data){
if(isFull()){
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
if(pos<0||pos>this.usedSize)return;
int i = this.usedSize - 1;
while(i>=pos){
this.elem[i+1] = this.elem[i];
i--;
}
this.elem[pos] = data;
this.usedSize++;
}
//打印
public void show(){
for(int i = 0;i < this.usedSize;i++){
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
//判断是否包含
public boolean contains(int n){
for(int i = 0;i < this.usedSize;i++){
if(this.elem[i] == n){
return true;
}
}
return false;
}
//查找某个元素对应位置
public int search(int val){
for(int i = 0;i < this.usedSize;i++){
if(val == this.elem[i]){
return i;
}
}
return -1;
}
//获取pos位置的元素
public int getPos(int pos){
if(this.usedSize==0)return -1;
if(pos<0||pos>=this.usedSize) {//?
return -1;
}
return this.elem[pos];
}
//获取长度
public int Size(){
return usedSize;
}
//删除第一次出现的关键字
public void deleteKey(int del){
int index = search(del);
for (int i = index; i < this.usedSize - 1;i++){
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
}
//清空顺序表
public void clear(){
this.usedSize = 0;
}
}