[数据结构与算法]数据结构作业:线性表的链式实现

**

线性表的链式实现

**
为LinkListWithSize类增加:
1、实现就地逆置函数：
public void reverse()
2、public void removeRange(int from, int to)
删除位置[from, to]范围的数据
3、public int lastInsdex(AnyType x)
返回x最后一次出现的位置

 public void reverse() {
	Node<T> p = head;
	for (int left = 0, right = size()-1;left<right;right--,left++){
		Node<T> q= head;
		
		for (int i = 0; i < right; i++)
			q = q.next;
			
		T temp = p.data;
		p.data = q.data;
		q.data = temp;
		p = p.next;
	}
}
public void removeRange(int from, int to) {
	if (from>to)
		return ;
	checkElementIndex(from);
	checkElementIndex(to);
	Node<T> p = head;
	for (int i = 0; i < from; i++)
		p = p.next;
	for(int i = from;i<=to;i++)
		remove(from);
}
public int lastInsdex(T x) {
	int number = -1;
    int index = -1;
    for (Node<T> p = head; p != null; p = p.next) {
       	index++;
        if (p.data.equals(x))
        	number = index;
    }
    return number;
}

不用remove的实现方法

 public void removeRange(int from, int to) {
		checkElementIndex(from);
		checkElementIndex(to);
        if (from>to)
            return;
		 if (from == 0)
            for (; from <= to; from++)
                head = head.next;
        else{
            Node<T> p = head;
            for (int i = 0; i < from-1; i++)
                p = p.next;
            Node<T> q = p;
            for (int i = from;i <= to;i++)
                q = q.next;
            p.next=q.next;
		}
    }

类内原有代码

public void removeRange(int from, int to) {
		if (from>to)
			return ;
		checkElementIndex(from);
		checkElementIndex(to);
		Node<T> p = head;
		for (int i = 0; i < from; i++)
			p = p.next;
		for(int i = from;i<=to;i++)
			remove(from);
    }
    public int lastInsdex(T x) {
		int number = -1;
        int index = -1;
        for (Node<T> p = head; p != null; p = p.next) {
           	index++;
            if (p.data.equals(x))
            	number = index;
        }
        return number;
    }
	private static class Node<T> {// 注意和Itr的比较，通过这个例子，应该能明白静态嵌套类和内部类的使用场合
		T data;
		Node<T> next;

		Node(T data, Node<T> next) {
			this.data = data;
			this.next = next;
		}
	}

    private Node<T> head;
    private int size;

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public int indexOf(T x) {
        int index = 0;
        for (Node<T> p = head; p != null; p = p.next) {
            if (p.data.equals(x))
                return index;
            ++index;
        }
        return -1;
    }

    // 将位置的合法性检查抽出作为方法
    private void checkPositionIndex(int index) {// insert用
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException(String.valueOf(index));
    }

    private void checkElementIndex(int index) {// 其它方法用，如果为空表，则会抛出异常
        if (index < 0 || index > size - 1)
            throw new IndexOutOfBoundsException(String.valueOf(index));
    }

    public T get(int index) {
        checkElementIndex(index);
        Node<T> p = head;
        // 找到结点index
        for (int i = 0; i < index; i++)
            p = p.next;
        return p.data;
    }

    public void add(int index, T x) {
        checkPositionIndex(index);
        if (index == 0) {// 空表，及插入位置0
            head = new Node<>(x, head);
        } else {
            Node<T> p = head;
            // 找到第i-1个结点
            for (int i = 0; i < index - 1; i++)
                p = p.next;
            p.next = new Node<>(x, p.next);
        }
        ++size;
    }

    public T remove(int index) {
        checkElementIndex(index);
        Node<T> p = head;
        if (index == 0) {// 肯定不为空
            head = head.next;
        } else {// 至少有2个结点
            // 找到待删除结点的前驱
            for (int i = 0; i < index - 1; i++)
                p = p.next;
            Node<T> q = p;
            p = p.next;
            q.next = p.next;
        }
        // p引用待删除结点
        T value = p.data;
        p.data = null;// 帮助GC
        p.next = null;
        --size;
        return value;
    }

    public void clear() {
        while (head != null) {// 从第1个节点开始，逐个删除
            Node<T> q = head;// q待删除节点
            head = head.next;// 下一个节点
            q.data = null;// 帮助GC
            q.next = null;
        }
        size = 0;
    }

    public String toString() {
        StringBuilder str = new StringBuilder(getClass().getName() + ":");
        for (T elem : this)//利用了实现了的迭代器
            str.append(elem).append("  ");
        return str + "\n";
    }

    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj instanceof LinkedListWithSize<?> rhd) {
            if (this.size != rhd.size)
                return false;
            for (Node<?> p = head, q = rhd.head; p != null; p = p.next, q = q.next) {
                if (!p.data.equals(q.data))
                    return false;
            }
            return true;
        } else
            return false;
    }

    public int hashCode() {
        int result = Integer.valueOf(size).hashCode();
        for (Node<T> p = head; p != null; p = p.next)
            result = result * 31 + p.data.hashCode();
        return result;
    }

    @SuppressWarnings("unchecked")
    private LinkedListWithSize<T> superClone() {
        try {
            return (LinkedListWithSize<T>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    public Object clone() {
        LinkedListWithSize<T> v = superClone();// v的head和size与this的head和size相同
        if (v.head == null) {
        } else {// 为v分配新的结点，不能与this共用
            v.head = new Node<>(head.data, null);
            for (Node<T> p = head.next, q = v.head; p != null; p = p.next, q = q.next)
                q.next = new Node<>(p.data, null);
        }
        return v;
    }

    public Iterator<T> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<T> {// 注意Itr是内部类，而 Node是静态的嵌套类
        private Node<T> curPos;

        public Itr() {
            curPos = head;
        }

        public boolean hasNext() {
            return curPos != null;
        }

        public T next() {
            T data = curPos.data;
            curPos = curPos.next;
            return data;
        }
    }

测试方法:

 public static void main(String[] args) {
        LinkedListWithSize<Integer> lk = new LinkedListWithSize<>();
        lk.add(0, 1);
        lk.add(0, 2);
        lk.add(0, 3);
        lk.add(0, 4);
        lk.reverse();
        System.out.println(lk);
        System.out.println(lk.lastInsdex(2));
		System.out.println(lk.lastInsdex(4));
		System.out.println(lk.lastInsdex(5));
		lk.removeRange(0,1);
		System.out.println(lk);
	}