|
链表简介：
? ? ? ? 就向链子一样，链表可以把一组数据元素串起来。
? ? ? ? 链表不像数组，链表在物理存储单元上非连续、非顺序，是通过存储数据元素时顺带储存了这个数据元素应该在的位置信息，打个比方，体育老师给同学排体操队形，让同学们每次做操的时候都按这个队形集合，学生小明记住了他前面是小红，小红记住了她前面是小爱因斯贝伦，那么每次集合时，他们都会这么站。假设这个班人均福尔摩斯，可以控制自己记住什么、不记什么，那么为了站好队，只记住自己后面一位同学，这就是单向链表，记住自己前后各一名同学，这就是双向链表。
? ? ? ?单向链表缺点：慢。如果一组数据很大，却用了单向链表存储，那么最经典的二分法也就用不了了，只能从前往后一一遍历，这必然慢。不如用换汤不换药的双向链表。然而存储前后两个位置必然比只存储后面位置多用空间，这也是一个典型的以空间换时间案例。
实现：
? ? ? ? 直接上代码，这是老师的作业，老师给了方法名与形参，写了Node<E>类与addFirst(E e)、addLast(E e)方法。学识浅薄，谢谢各位指出错误！
public class MyListImpl<E>? {
?? ?private Node<E> head;//头引用
?? ?private Node<E> tail; //尾引用
?? ?private int size;
?? ?public static void main(String args[]) throws Exception{
?? ??? ?MyListImpl<String> list = new MyListImpl<String>();
?? ??? ?list.add("I_AM_HEAD");
?? ??? ?list.add("I_AM_TAIL");
?? ??? ?list.add(1,"I_CAN_PUSH_IN_THE_LIST");
?? ??? ?list.add(2,"I_WILL_BE REMOVED");
?? ??? ?list.add(3,"I_WILL_BE_SET");
?? ??? ?list.add(4,"I_WILL_BE_REMOVED_BY_DATA");
?? ??? ?
?? ??? ?System.out.println("List before operations");
?? ??? ?for(int i = 0; i < list.size; i++) {
?? ??? ??? ?System.out.println(list.get(i));
?? ??? ?}
?? ??? ?System.out.println(list.size);
?? ??? ?list.update(3, "I_HAVE_UPDATED_HIM");
?? ??? ?list.remove(2);
?? ??? ?list.remove("I_WILL_BE_REMOVED_BY_DATA");
?? ??? ?
?? ??? ?System.out.println("\nList after operations");
?? ??? ?System.out.println(list.get(0));
?? ??? ?System.out.println(list.get(1));
?? ??? ?System.out.println(list.get(2));
?? ??? ?System.out.println(list.get(3));
?? ??? ?System.out.println(list.size);
?? ??? ?
?? ?}
?? ?public void addFirst(E e) {
?? ??? ?final Node<E> first = head;
?? ??? ?final Node<E> newNode = new Node<>(e, null, first);//head是next，创建一个新的node
?? ??? ?
?? ??? ?head = newNode;//再把新的node重新赋给head,这样的话head还是第一位
?? ??? ?
?? ??? ?if(first==null) {//如果原来的head是空，就是说这个列表没有元素
?? ??? ??? ?tail = newNode;//直接到尾，并且尾的next也是空，但新的head是形参e
?? ??? ?}else {
?? ??? ??? ?first.prev = newNode;//如果原来的head不为空，
?? ??? ??? ??? ??? ??? ??? ??? ? //至少有一个元素，就可以把原来的head前加上一个新的元素，也就是存储了e的newCode
?? ??? ??? ??? ??? ?
?? ??? ?}
?? ??? ?size++;
?? ??? ?
?? ?}
? ??
?? ?public void addLast(E e) {
?? ??? ?final Node<E> last = tail;
?? ??? ?final Node<E> newNode = new Node<>(e, last,null);/*
?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?*同理，新的tail以原来的tail为prev，没有next
?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?*/
?? ??? ?tail = newNode;
?? ??? ?
?? ??? ?if(last == null) {
?? ??? ??? ?head = newNode;
?? ??? ?}else {
?? ??? ??? ?last.next = newNode;
?? ??? ?}
?? ??? ?size++;
?? ??? ?
?? ?}
?? ?
?? ?/**
?? ? * 普通的添加元素直接向最后缀上元素就OK了
?? ? */
?? ?public void add(E e) {
?? ??? ?addLast(e);
?? ??? ?
?? ?}
?? ?/**
?? ? * 通过index在指定位置添加元素
?? ? * 要考虑到添加元素后，这个位置前一位与后一位两个Node他们的链接关系会发生变化
?? ? */
?? ?public void add(int index, E e) throws Exception{
?? ??? ?if(head == null) {
?? ??? ??? ?addFirst(e);
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?if(index == size) {
?? ??? ??? ?addLast(e);
?? ??? ??? ?return;
?? ??? ?}
?? ??? ?if(index > size) {
?? ??? ??? ?throw new Exception("Actually it's an Add Exception, index is out of the range of size");
?? ??? ?}
?? ??? ?Node<E> temp = head;
?? ??? ?for(int i = 0; i < index-1; i++) {
?? ??? ??? ?temp = temp.next;
?? ??? ?}
?? ??? ?Node<E> newList = new Node<E>(e, temp, temp.next);
?? ??? ?Node<E> test = temp.next;//这名字取得显然不好，此处也可以简单优化下
?? ??? ?temp.next = newList;//感谢java是值传递，temp指向的就是那个位置的Node，直接对它操作就OK了
?? ??? ?test.prev = newList;
?? ??? ?size++;
?? ?}
?? ?/**
?? ? * 通过index去消去某个元素
?? ? * 思路是找到它，再改变它前后位链接的元素，让它前一位的next是它后一位，无视掉它就好了
?? ? */
?? ?public void remove(int index) throws Exception{
?? ??? ?if(index < 0 || index > size) {
?? ??? ??? ?throw new Exception("Actually it's a Remove Exception, index is out of the range of size");
?? ??? ?}
if(index == 0) {
head = head.next;
head.prev = null;
size --;
return;
}
if(index == size - 1) {
tail = tail.prev;
tail.next = null;
size --;
return;
}
?? ??? ?Node<E> temp = head;
?? ??? ?for(int i = 0; i < index-1; i++) {
?? ??? ??? ?temp = temp.next;
?? ??? ?}
?? ??? ?Node<E> test = temp.next.next;
?? ??? ?temp.next = temp.next.next;
?? ??? ?test.prev = temp;
?? ??? ?size--;
?? ??? ?
?? ?}
?? ?/**
?? ? * 与ArrayList同样是用了equals
?? ? * 遍历找到它的位置，用之前的remove搞定
?? ? * 两次遍历，挺冗长的
?? ? */
?? ?public void remove(E e) throws Exception{
?? ??? ?
?? ??? ?for(int i = 0; i < size; i++) {
?? ??? ??? ?if(this.get(i).equals(e)) {
?? ??? ??? ??? ?this.remove(i);
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?/**
?? ? * 更新这个元素，也就是set（老师习惯叫update）
?? ? * 用之前写好的增删查去实现改
?? ? */
?? ?public void update(int index, E e) throws Exception{
?? ??? ?if(this.get(index) != null) {
?? ??? ??? ?
?? ??? ??? ?this.remove(index);
?? ??? ??? ?this.add(index,e);
?? ??? ?}
?? ?}
?? ?
?? ?/**
?? ? * 正向遍历查找
?? ? */
?? ?public E get(int index) {
?? ??? ?Node<E> temp = head;
?? ??? ?for(int i =0;i<index;i++) {
?? ??? ??? ?temp =temp.next;
?? ??? ?}
?? ??? ?return temp.data;
?? ?}
?? ?
?? ?private static class Node<E>{
?? ??? ?E data;
?? ??? ?Node<E> prev;//用于记录这个位置的前一个位置是什么
?? ??? ?Node<E> next;
?? ??? ?
?? ??? ?public Node(E data, Node<E> prev, Node<E> next) {
?? ??? ??? ?super();
?? ??? ??? ?this.data = data;
?? ??? ??? ?this.prev = prev;
?? ??? ??? ?this.next = next;
?? ??? ?}
?? ??? ?
?? ??? ?
?? ?}
}
|