目录

前言

一、主要思路

二、主要步骤

0.节点对象

1.链表对象

2.构造方法

3.检查是否符合要求

4.尾插

5.给定下标插入

6.给定下标删除

7.获取指定下标的元素

8.修改指定下标的元素

9.输出指定元素的下标

10.输出链表是否包含指定元素

11.给定元素删除第一个

12给定元素删除全部

总结

---

前言

        以前我们实现的都是节点对象，现在我们需要完成一个双向的无头的不循环的链表对象。主要包含的方法如下：

尾插、给定下标插入、给定下标删除、给定元素删除、给定元素删除全部、获取指定下标的元素、修改指定下标的元素、输出指定元素的下标。判断指定元素是否在链表之中。

一、主要思路

        基本上都是一些较为简单的功能，但是我们需要注意到特殊情况，如当链表为空，当链表元素为一个等情况。所以我们检查对象的时候也需要比较小心。

二、主要步骤

0.节点对象

        由于是双向的无头的不循环的链表，貌似和单链表的实现方法区别不大。如下：

public class Node {public long val;public Node prev;public Node next;public Node(long val) {this.val = val;}public Node(long val, Node prev, Node next) {this.val = val;this.prev = prev;this.next = next;}
}

1.链表对象

        首先我们需要记录链表的大小，然后由于是双向的链表，我们需要记录头节点和尾节点。如下：

    private int size;private Node head;private Node last;

2.构造方法

        构造方法，基本上就是需要的时候再往里添加。如下：

    public LinkedList() {head=last=null;size=0;}

3.检查是否符合要求

        检查一个链表对象是否符合规范需要考虑的情况就比较多了。我们可以分成链表为空，链表只有1个元素，链表有多个元素来讨论。对于这些情况我们还需要讨论头结点、尾节点、中间节点以及链表的size是否符合要求。如果不符合要求，我们需要抛出异常。其中还用到了计算size的方法。整体如下：

    public void check(){if(size==0){if(head!=null||last!=null){throw new RuntimeException("");}}else if(size==1){if(head==null||last==null||head!=last){throw new RuntimeException("");}if(head.prev!=null||last.next!=null){throw new RuntimeException("");}}else{//检查size是否符合要求int aSize=calcSize(head);if(size!=aSize){throw new RuntimeException("");}else {//检查头节点if(head==null){throw new RuntimeException("");}if(head.prev!=null){throw new RuntimeException("");}if(head.next.prev!=head){throw new RuntimeException("");}//检查尾节点if(last==null){throw new RuntimeException("");}if(last.next!=null){throw new RuntimeException("");}if(last.prev.next!=last){throw new RuntimeException("");}//检查中间节点Node cur=head.next;while(cur!=last){if(cur.next.prev!=cur){throw new RuntimeException("");}if(cur.prev.next!=cur){throw new RuntimeException("");}cur=cur.next;}}}}private int calcSize( Node head){int s=0;for (Node c=head;c!=null;c=c.next){s++;}return s;}

4.尾插

        我们开始主要的方法的实现，尾插比较简单，分情况就行。如下：

    public void add(long e){Node node=new Node(e);if(size==0){head=last=node;size++;}else{last.next=node;node.prev=last;last=node;size++;}}

5.给定下标插入

        给定下标插入就相对尾插要复杂一些。主要是要分的情况比较多，首先当size分别为0或者1或者其他自然数时，并且当插入的位置是头或者尾或者中间的时候都需要分情况讨论。如下：

    public void add(int index,long e){Node node = new Node(e);if(index<0||index>size){throw new RuntimeException("");}if(size==0){add(e);}if(size==1){if(index==0){node.next=head;head.prev=node;head=node;size++;}if(index==1){node.prev=last;last.next=node;last=node;size++;}}else{if(index==0){node.next=head;head.prev=node;head=node;size++;}else if(index==size){node.prev=last;last.next=node;last=node;size++;}else{Node cur=head;for (int i = 0; i < index; i++) {cur=cur.next;}cur.prev.next=node;node.prev=cur.prev;node.next=cur;cur.prev=node;size++;}}}

6.给定下标删除

        和指定下标插入一样，需要考虑什么时候抛出异常，可以删除的时候分为哪些情况，这些情况需要怎么删除。如下：

    public long remove(int index){if(index<0||index>=size){throw new RuntimeException("");}else{long val=0;if(size==1){val=head.val;head=last=null;size--;}else if(size==2){if(index==0){val= head.val;head=head.next;head.prev=null;size--;}if(index==1){val= last.val;last=last.prev;last.next=null;size--;}}else{if(index==0){val= head.val;head=head.next;head.prev=null;size--;}else if(index==size-1){val= last.val;last=last.prev;last.next=null;size--;}else{Node cur=head;for (int i = 0; i < index; i++) {cur=cur.next;}val= cur.val;cur.prev.next=cur.next;cur.next.prev=cur.prev;size--;}}return val;}}

7.获取指定下标的元素

        获取指定下标的元素比较简单。如下：

    public long get(int index){if(index<0||index>=size){throw new RuntimeException("");}else{Node cur=head;for (int i = 0; i <index ; i++) {cur=cur.next;}return cur.val;}}

8.修改指定下标的元素

        同理，如下：

    public long set(int index,long e){if(index<0||index>=size){throw new RuntimeException("");}else{Node cur=head;for (int i = 0; i <index ; i++) {cur=cur.next;}long oldVal=cur.val;cur.val=e;return oldVal;}}

9.输出指定元素的下标

        这几个方法都比较简单，会遍历就行。如果没有指定元素就输出-1。如下：

    public int indexof(long e){int index=0;for(Node cur=head;cur!=null;cur=cur.next){if(cur.val==e){return index;}index++;}return -1;}

10.输出链表是否包含指定元素

        这个方法只要结合上个方法就行了如下：

    public boolean contains(long e){return indexof(e) != -1;}

11.给定元素删除第一个

        这个方法也是结合了indexof和remove方法。

    public void delete(long e){int index=indexof(e);if(index!=-1){remove(index);}}

12给定元素删除全部

        这个方法有两种实现方法，如果想偷懒，直接用之前的方法融合就行。但是我们可以实现一个遍历一遍就删除的方法。如下：

    public void deleteAll(long e){Node cur=head;while(cur!=null){if(cur.val==e){if(size<=1){head=last=null;size=0;}else if(size==2){if(cur==head){head=head.next;head.prev=null;size--;}else{last=last.prev;last.next=null;size--;}}else{if(cur==head){head=head.next;head.prev=null;size--;}else if(cur==last){last=last.prev;last.next=null;size--;}else{cur.prev.next=cur.next;cur.next.prev=cur.prev;size--;}}}cur=cur.next;}}

总结

        一个简单的链表对象就完成了。还需要更加熟练。