恋上数据结构-03链表-01

恋上数据结构-03链表-01 链表（linked List） 动态数组（Dynamic Array Or ArrayList）有一个明显的缺点

• 可能会造成内存空间的大量浪费

能否用到多少内存就分配多少内存

• 链表可以做到这一点

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

链表的设计

链表linkedList包括元素个数size以及头结点first两个成员变量
每一个节点中又包括本节点特征元素element以及对下一个节点的引用next

接口设计 链表的大部分接口和动态数组是一致的

• 由于ArrayList与linkedList的方法基本一致，但是很多方法的实现是完全不同的。因此可以使用一个接口声明所有的方法，使得这两个类可以通过实现同一个List接口,实现同样的功能。

public interface List {
	//接口类由于供实现他的类使用，因此默认都是public
	static final int ELEMENT_NOT_FOUND = 0;
	 
	int size();
	
	boolean isEmpty();
	
	boolean contains(E element);
	
	void add(E element);
	
	
	E get(int index);
	
	E set(int index, E element);
	
	void add(int index, E element);
	
	
	E remove(int index);
	
	int indexOf(E element);
	
	void clear();
	
	//====以下是一些工具方法=========//
	
	void ensureRangeInternal(int index);
	
	void ensureRangeOnAdd(int index);

• 由于List定义的方法中，有一些方法的实现是完全一样的，这些方法在两个类中重复实现很冗余，但是接口List又无法实现，这时我们就可以定义一个抽象类AbstractList实现接口List,并将在链表和动态数组中相同的实现方法在抽象类中实现，根据Java中抽象类的特性，其他不同实现的方法完全可以不用管，交给子类实现即可，因此可以让ArrayList与linkedList都继承AbstractList,这样就只需要重写需要的方法即可。

public abstract class AbstractList implements List{

	
	//也是公共代码的一部分要对子类可用
	protected static int size = 0;
	
	@Override
	public int size() {
		return size;
		// TODO Auto-generated method stub
		
	}

	
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}

	
	@Override
	public boolean contains(E element) {
		// TODO Auto-generated method stub
		return indexOf(element) == List.ELEMENT_NOT_FOUND;
	}

	
	@Override
	public void add(E element) {
		add(size, element);
		// TODO Auto-generated method stub
		
	}

	
	@Override
	public void ensureRangeInternal(int index) {
		// TODO Auto-generated method stub
		if (index < 0 || index >= size) {
			throw new IndexOutOfBoundsException("inex out of bound");
		}
	}

	
	@Override
	public void ensureRangeOnAdd(int index) {
		// TODO Auto-generated method stub
		if (index < 0 || index > size) {
			throw new IndexOutOfBoundsException("index out of bound");
		}
		
	}

• 在动态数组的设计中，我们用到了常量ELEMENT_NOT_FOUND，这个常量现在应该放在哪里呢？首先抽象类abstract是不能new的，其次abstract抽象类只是为了抽取公共代码，对外界不可见的，但是常量如果是由子类调用，则对外可见，因此不能放在抽象类，，其次如果放在子类中，那么回造成冗余，因此最好还是放在接口List中，并且这样如果判断contiains,那么直接判断List.ELEMENT即可，不必自己在定义一个数字-1，List是一个接口，接口是供实现的，因此变量默认是public
• 其次对于变量size,由于我们抽取到abstract类中的代码需要size变量，因此需要将他放在抽象类中，又由于也是公共代码的一部分需要提供给子类使用，因此该变量不能私有，而是protected最好。

清空元素-clear()

实现方法

puvlic void clear(){
	head = null;
	size = 0; 
}

next需要设置为null吗;

不需要，因为head设置为null,则第一个元素不再被引用，则第一个元素可以被回收，同样第一个元素回收后，第二个元素不再被引用可以被回收，以此类推链表的内存都会被回收，不需要额外设置null;

添加元素 add(int index, E element)

添加元素考虑两种情况

添加首部情况

如果我们是添加首部，那么应该使得head指向新建的节点，并使得新建节点的指向的下一个节点是head,注意并不是head.next,我这里就是有点短路了，以为是head.next，我还在想怎么不考虑是空链表的情况，确实是傻了

if(index == 0){
	head = new Node(element, head);
}

其他部分添加情况

其他部分的添加就比较简单了，只要获取index-1个节点，新节点指向index-1节点的下一个节点，index-1节点再指向新节点即可。

pre.next = new Node(element, pre.next);

node方法用于获取index位置的节点

• 由于很多方法需要获取某一个index的节点，但是get返回的E类型的元素，因此就需要写一个私有方法，进行实现。这里我开始把检查索引的方法没有放在里面，在听老师讲了一遍才把他放了进来，也确实是这样。
• 这个循环是比较有意思的，因为不是数组没有序号，所以我们需要根据索引来判断循环多少次得到这个节点。

public Node note(int index){
	ensureRangeInternal(index);
	Note newHead = head;
	for(int i = 0; i < index; i ++){
		newHead = newHead.next;
	}
	return newHead;
}

删除元素 remove(int index)

删除元素也要考虑两种情况

删除首部

删除首部我们就不需要考虑空链表的情况了阴我我们在ensureRangeInternal中可以保证排除空链表的情况，那么排除空链表后，我们只需要将链表首部指向该首部的引用即可。

if(index == 0){
	head  = head.next;
}

删除其他部分

其他部分的话还是先拿到prev,然后prev.next=prev.next.next即可

Node prev = node(index-1);
prev.next = prev.next.next;

推荐神奇的网站

https://visualgo.net/zh

附上自己写的linkedList代码

package com.ldy;

import java.awt.HeadlessException;
import java.security.PublicKey;
import java.util.Iterator;



public class linkedList extends AbstractList{
	
	private  Node head;
	
	
	private static class Node{
		 E element;
		 Node next;
		public Node(E element, Node next) {
			this.element = element;
			this.next = next;
		}
		
	}
	
	@Override
	public E get(int index) {
		Node node = node(index);
		// TODO Auto-generated method stub
		return node.element;
	}

	@Override
	public E set(int index, E element) {
		//获取节点
		Node node = node(index);
		//获取旧元素
		E oldElement = node.element;
		//覆盖旧元素
		node.element = element;
		// TODO Auto-generated method stub
		return oldElement;
	}

	@Override
	public void add(int index, E element) {
		// TODO Auto-generated method stub
		//确保添加时索引正确
		ensureRangeOnAdd(index);
		//判断是否为空链表
		
		//添加在首部
		if (index == 0) {
			head  = new Node(element, head);
		}else {
			//找到索引所在节点
			Node prev = node(index-1);
			prev.next = new Node(element, prev.next);
			//如果是添加在尾部，也是可以满足的。
		}
		size ++;
		
		
	}

	
	@Override
	public E remove(int index) {
		// TODO Auto-generated method stub
		//确保索引正确
		ensureRangeInternal(index);
		size --;
		//获取原有节点；
		E oldElement;
		//如果是第一个头部
		if (index == 0) {
			oldElement = head.element;
			head = head.next;
			
		}else {
			//找到前驱节点
			Node prev = node(index-1);
			//得到原有节点内容
			oldElement= prev.next.element;
			//删除原有节点
			prev.next = prev.next.next;
		}
		
		
		return oldElement;
	}

	
	@Override
	public int indexOf(E element) {
		// TODO Auto-generated method stub
		//如果链表为空，就可以报错了
		if (head == null) {
			throw new NullPointerException();
		}
		//自定义链表则element是null是有可能的。
		Node newHead = head;
		//如果链表为空
		if(element == null) {
			for(int i = 0; i < size; i ++) {
				if (newHead.element == null) {
					return i;
				}
				newHead = newHead.next;
			}
			
		}else {
			//如果链表不为空
			for(int i = 0; i < size; i ++) {
				if (newHead.element.equals(element)) {
					return i;
				}
				newHead = newHead.next;
			}
		}
		//返回没有找到
		return ELEMENT_NOT_FOUND;
	}

	
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		//切断对第一个元素的引用，则第一个元素回收，
		//那么第二个元素引用也会消失，则第二个元素回收
		//以此类推，全都会回收。
		head = null;
		size = 0;
	}
	
	//===========内部工具类=============//
	
	private Node node(int index) {
		ensureRangeInternal(index);
		Node newHead = head;
		for(int i = 0; i< index; i ++) {
			newHead = newHead.next;
		}
		return newHead;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		Node newHead = head;
		StringBuilder builder = new StringBuilder();
		builder.append("size:").append(size).append(",[");
		for(int i = 0;i 
leetcode_237_删除链表中的节点 
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/ 
 
题目告诉我们无法访问head节点，就是在告诉我们，无法拿到目标节点的前驱节点， 只能通过用后继节点覆盖目标的节点的方式解题。
 我们要覆盖一个节点不是说直接改变地址引用，这样是做不出来的，而是将节点中所有的元素实现覆盖。比如
 
public class ListNode{
	int val;
	ListNode next;
}
 
我们就需要用后继节点的val元素覆盖原来的val,同时用后继节点的next覆盖原来的地址引用。即，
 
public void deleteNode(ListNode node){
	node.val = node.next.val;
	node.next = node.next.next;

}
 
_206_反转链表_递归 
https://leetcode-cn.com/problems/reverse-linked-list/submissions/ 

 根据题目描述，我们先选择用递归的方式解决。
 我的思路是，既然整个链表都需要反转，那么每一段长度递减的链表也都需要反转，这就有了递归的理论基础，每一个反转后的小链表加上递增链表的头部作为字迹的尾部即可，这样不断反推就可以得到反转链表。
 比如说1，加上递增链表21的头部2作为自己的尾部就是反转链表12，再比如说321，已经反转的12加上头部3作为自己的尾部就是反转链表123.
 因此我们首先要做的就是递推到只剩一个节点，这样本身就已经翻转了，然后开始不断加尾部反推。代码如下：
 
public ListNode reverseList(ListNode head) {
		//如果是空链表，或者只有一个节点的链表直接返回
		if (head == null || head.next == null) {
			return head;
		}
		//找到链表的尾部，作为新节点的头节点
		//这里要知道，head.next才是尾节点，返回的就是尾节点
		//也就是新链表的首节点
		ListNode newHead =  reverseList(head.next);
		//设置尾节点
        // ListNode oldEnd = head.next;
        // ListNode newEnd = oldEnd.next = head;
        //如果以后忘了就看上面的注释的两行，这样就可以避免从新的头部开始循环。
        head.next.next = head;
		//尾节点的后继肯定是null
		head.next = null;
		//返回新节点的头节点
		return newHead;

    }
 
这里还有几个关键点
 
首先当空链表和只有一个节点的链表本身就是反转的，直接返回就行
其次，反转链表增加自己的尾部，有两种方式，一种是利用while循环，从首部遍历到尾部；这样多了一个循环耗时；另一种方式是利用head节点，我们反转节点的尾部是oldEnd = head.next,我们需要新增的尾部是head节点，那么使得(head.next).next = head即可完成。减少时间损耗。
最后尾部即head，他的后继节点依旧是oldEnd,成了一个环形，因此必须将head的后继设置为null.
 
_206_反转链表_迭代 
https://leetcode-cn.com/problems/reverse-linked-list/submissions/ 

 老师这张图真的是非常形象了，看的很清楚，自己再把思路复述一遍。
 迭代的思路也很简单，应该说是拆拆拆，
 
我们需要三个指针， head, second以及newHead
 first指向链表头部，second指向head的后继节点，newHead作为新链表的首部。
开始的时候先让second指向first的后继节点，然后将head的后继节点指向newHead, newHead一开始为空，second一开始也为空，然后将newHead指向first节点，将first指向second节点
以上的文字说明就是不断拆原来的链表，构造新链表的过程，只要head不是null，就可以不断的循环，直到构造完成。
这里我开始的时候时second不是空，所以还在循环之外写了一些代码，现在看来是不必要的。
 
代码如下 
public ListNode reverseList(ListNode head) {
		
		//迭代性能一般都比递归要高，因为一个是O（N）一个是O(N^2)
        if(head == null || head.next == null) return head;
		
		ListNode second = null;
		ListNode newHead = null;
		while(head != null) {
			second = head.next;
			head.next = newHead;
			newHead = head;
			head = second;
			
		}
		
		return newHead;

    }
 
_141_环形链表 
https://leetcode-cn.com/problems/linked-list-cycle/submissions/ 

 环形链表用快慢指针解决，思路还是很简单的
 我们将第一个指针指向头部，第二个指针指向头部后继节点，第一个指针一次走一个单位，第二个指针一次走两个单位，如果有环的话，就像是在跑圈，跑得快的和跑的慢的，总会套圈相遇
 代码实现如下：
 
    public boolean hasCycle(ListNode head) {
    	if(head == null || head.next == null) return false;
		ListNode first = head;
		ListNode second = head.next;
		//只要两个指针指向节点的val相同就可以认为是有环
		while(second != null && second.next != null) {
			// if(second.val == first.val && second.next == first.next) {
			// 	return true;
			// }
            if(first == second) return true;
			first = first.next;
			second = second.next.next;
		}
    	return false;
        
    }
 
已经快十点了今天就先到这里，明天在继续研究链表，明天还有一个面试哎啥都不会。
 
快指针走两步，而不是走三步甚至四步的原因 
可以想象一下，如果快慢指针间隔5步，那么下一轮次慢指针走一步，快指针走两步，双方距离缩短到4，那么继续下一轮双- 方轮次缩短到3，继续2，1直到相遇，也就是说快指针走两步可以保证一定相遇
如果快指针走三步，会发生什么呢？假设距离还是5，那么下一轮慢指针走一步，快指针走三步，距离缩短到3，再下一轮缩短到1，在下一轮缩短到-1，也就是说发生了套圈！相遇需要的时间就多了。
慢指针走两步，快指针走三步呢？这个效果好像是一样的，但是循环控制条件就要写的更多了。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5686200.html