最近在看JAVA教学的视频,觉得老师讲的很好,同时借用源代码还有笔记来撰写本系列博客,记录自己的学习内容,同时也供看到的人学习。
昨天生病了木有写博文~今天继续,第30篇,本篇内容的类型和上一篇是一样的,模拟实现另外一种实现List接口的数据结构:双向链表——LinkedList,还是直接呈上代码,关于部分方法的解释讲解我已经添加到了代码里面,看此博文的小伙伴要仔细阅读或者实现一下,便于我们更加深入地理解:
//用来表示一个节点
public class Node {
Node previous; //上一个节点
Object obj; //节点的本质(值)是Object型
Node next; //下一个节点
public Node() {
}
public Node(Node previous, Object obj, Node next) {
super();
this.previous = previous;
this.obj = obj;
this.next = next;
}
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
public Object getObj() {
return obj;
}
public void setObj(Object obj) {
this.obj = obj;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
package cn.bjsxt.collection;
public class SxtLinkedList /*implements List*/ {
private Node first; //获得头结点,之后按照Node的结构可以一直往后找
private Node last; //获得当前链表的最后一个节点
private int size;
public void add(Object obj){
Node n = new Node();
if(first==null){ //链表中没有任何结点的情况下
n.setPrevious(null); //因为是头结点所以Previous为空
n.setObj(obj);
n.setNext(null); //后面由于暂时没有结点所以也为空
first = n; //目前第一个和最后一个都是该节点
last = n;
}else{
//直接往last节点后增加新的节点
n.setPrevious(last);
n.setObj(obj);
n.setNext(null);
last.setNext(n);
last = n;
}
size++;
}
public int size(){
return size;
}
private void rangeCheck(int index){
if(index<0||index>=size){
try {
throw new Exception();
} catch (Exception e) {
e.printStackTrace();
}
}
}
public Object get(int index){ //2
rangeCheck(index);
// 0 1 2 3 4
Node temp = node(index);
if(temp!=null){
return temp.obj;
}
return null;
}
public Node node(int index){ //按索引找到相应节点的方法,实现List接口必须有的
Node temp = null;
if(first!=null){
if (index < (size >> 1)) { //如果索引号是前半部分的则从头结点开始遍历查找
temp = first;
for(int i=0;i<index;i++){
temp = temp.next;
}
}else{
temp = last; //如果索引号是后半部分的则从尾结点开始遍历查找
for (int i = size - 1; i > index; i--){
temp = temp.previous;
}
}
}
// LinkedList l;
return temp;
}
public void remove(int index){
Node temp = node(index);
if(temp!=null){ //数据结构的知识,不再详述~
Node up = temp.previous;
Node down = temp.next;
up.next = down;
down.previous = up;
size--;
}
}
public void add(int index,Object obj){
Node temp = node(index);
Node newNode = new Node();
newNode.obj = obj;
if(temp!=null){
Node up = temp.previous;
up.next = newNode;
newNode.previous = up;
newNode.next = temp;
temp.previous = newNode;
size++;
}
}
public static void main(String[] args) {
SxtLinkedList list = new SxtLinkedList();
list.add("aaa");
list.add("bbb");
// list.add(1,"BBBB");
list.add("ccc");
list.add("ddd");
list.add("eee");
// list.remove(1);
System.out.println(list.get(3));
}
}