这是系列文章,每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现,从而对常用的数据结构和
java
集合有个大概的了解。当然实现没有java
集合的实现那么复杂,功能也没有那么强大,但是可以通过这些简单的实现窥探到底层的一些共性原理。
一. 线性表的描述
线性表是其组成元素之间具有线性关系的一种线性结构,比如java
集合框架里面的ArrayList
和LinkedList
等都是典型的线性表。对线性表的基本操作主要有插入,删除,查找,替换等。这些操作可以在线性表的任何位置进行。线性表可以采用顺序存储结构
和链式存储结构
来表示,采用顺序存储结构表示就是顺序表,比如ArrayList
,采用链式结构表示就是链表,比如LinkedList
。
二.线性表的操作
线性表接口LList
声明如下,描述线性表的取值,置值,插入,删除等基本操作。
package org.light4j.dataStructure.linearList;
public interface LList<E> { //线性表接口
boolean isEmpty(); //判断线性表是否为空,若为空则返回true
int length(); //返回线性表长度
E get(int index); //返回序号为index的对象,index初始值为0
E set(int index,E element); //设置序号为index对象为element,返回原对象
boolean add(int index,E element); //插入element对象,插入后对象序号为index
boolean add(E element); //插入element对象,插入位置没有约定
E remove(int index); //移去序号为index的对象,返回被移去对象
void clear(); //清空线性表
}
顺序表类和链表类需要实现LList
接口,并对LList
接口中定义的方法给出具体的实现。例如顺序表类和单链表类的定义如下:
public class SeqList<E> implements LList<E> //顺序表类
public class SinglyLinkedList<E> implements LList<E> //单链表类
LList
接口中的方法在顺序表和链表类中表现出多态性。关于顺序表和单链表的具体实现细节在后面会有文章详细讲到,可以点击下面地址查看。
自己实现集合框架(二):顺序表的实现
自己实现集合框架(三):单链表的实现
三.源代码示例
公众号ID:longjiazuoA

未经允许不得转载:人生设计师 » 自己实现集合框架(一):线性表接口
可以了,再试下。