[数据结构与算法]暑期的数据结构学习（Java）4.0(链表)

4.0链表

class Node{
E e;
Node next;
}

优点：真正的动态，不需要处理固定容量的问题；
?
缺点：丧失了随机访问的能力
?
数组最好索引有语义的情况，有点支持快速查询
?
链表不适合用于索引有语义的情况，优点动态

public interface Stack<E>{
? ? int getSize();
? ? boolean isEmpty();
? ? void push(E e);
? ? E pop();
? ? E peek();
}
public class LinkedList<E>{
? ? private class Node{
? ?? ???public E e;
? ?? ???public Node next;
? ?? ???
? ?? ???public Node(E e,Node next){
? ?? ?? ?? ?this.e =e;
? ?? ?? ?? ?this.next =next;
? ?? ???}
? ?? ?? ?public Node(E e){
? ?? ?? ?? ?this(e,null);
? ?? ?? ?? ? public Node(){
? ?? ?? ?? ?? ???this(null,null);
? ?? ?? ?? ? }
? ?? ?? ?? ?
? ?? ?? ?? ? public String toString(){
? ?? ?? ?? ?? ???return e.toreSting();
? ?? ?? ?? ? }
? ?? ?? ?? ?
? ?? ?? ?? ?
? ?? ?? ?? ?
? ?? ???}
? ? }
}

4.1添加元素

private Node head;
int size;
public LinkedList(){
? ? head=null;
? ? size = 0;
? ?
}
//获取个数
public int getSize(){
? ? return size;
? ?
}
public boolean isEmpty(){
? ? return size==0;
}

4.1.2表头添加元素

public void addFirst(E e){
Node node = new Node(e);
node.next=head;
head =node;
//head = new Node(e,head);
size==;
}

4.1.2中间添加元素??//在链表中不是一个常用的操作

public void add(int index,E e){
? ? if (index <0||index>size)
? ? {throw new illegalArgumentException("error");
? ? }if (index === 0){
? ?? ???addFirst(e);
? ?? ???else{Node temp =head;
? ?? ?? ?? ?for (int i =0;i<index-1;i++)
? ?? ?? ?? ?temp = temp.next;
? ?? ?? ?? ?
? ?? ?? ?? ? Node node = new Node(e);
? ?? ?? ?? ? node.next=temp.next;
? ?? ?? ?? ? temp.next =node;
? ?? ?? ?? ?
? ?? ?? ?? ? size++;
? ?? ?? ?? ?}
? ? }
}
//同理末尾添加
public void adLast(E e){
add(size,e);
}

4.3优化使用虚拟头节点

public LinkedList(){
? ? dummyHead = new Node(null,null);
? ? size = 0
}public void add(int index,E e){
? ? if (index == 0)
? ?? ???addFirst(e);
? ?? ???else{Node temp =dummyHead;
? ? }
? ? //这里只截取了修改的片段
}

4.4链表的遍历，查询，修改（只作为练习用

public E get(int index){
? ? //一个合法性的判断，之前写到了，这里不再重复
? ?
? ? //开始遍历
? ? Node cur= dummyHead.next;
? ? for(int i=0;i<index;i++){//这里从第一个元素开始遍历，而上面是从第一个的前一个开始遍历
? ?? ???cue = cur.next;
? ?? ???return cur.e;
? ? }
}
?
?
public E grtFirst(){
? ? return get(0);
}
public E grtLast(){
? ? return get(size-1);
}//修改元素
public void set(int index,E e)
{ //一个合法性的判断，之前写到了，这里不再重复
? ? Node cur = dummyHead.next;
? ? for (int i=0;i<index;i++)
? ? {
? ?? ???cur = cur.next;
? ?? ???cur.e=e;
? ? }
}//查找元素
public boolean contains(E e){
? ? Node cur = dummyHead.next;
? ? while(cur !=null){
? ?? ???if (cur.e.equals(e))
? ?? ?? ?? ?return ture;
? ?? ???cur = cur.next;
? ? }
? ? return false;
}
//打印
public String toString(){
? ? StringBuilder res = new StringBuilder();
? ? Node cur = dummyHead.next;
? ? while(cur ！= null){
? ?? ???res.append(cur +"->");
? ?? ???cur = cur.next;
? ? }
? ? res.append("null");
? ? return res.toString();
? ?
}

4.5删除元素

public E remove(int index){
? ???//一个合法性的判断，之前写到了，这里不再重复
? ? Node prev = demmyHead;
? ???for (int i=0;i<index;i++)
? ?? ? prev = prev.next;
? ? Node retNode = prev.next;
? ? prev.next = retNode.next;
? ? retNode.next = null;
? ? size--;
? ? return retNode.e;
}
? ? public E removeFirst(){
? ?? ???return remove(0);
? ? }??
public E removeLast(){
? ?? ???return remove(size-1);
? ? }

?

4.6使用链表实现栈

public class LinkedListStack<E> implements Stack<E>{
? ? private LinkedListStack(){
? ?? ?list = new LinkedList<>();
? ? }
? ? public int getSize(){
? ?? ???return list.getSize();
? ?? ???
? ? }
? ? public boolean isEmpty(){
? ?? ???return list.isEmpty();
? ? }
? ? public void push(E e){
? ?? ???list.addFirst(e);
? ? }
? ? public E pop(){
? ?? ???return list.removeFirst();
? ? }
? ? public E peek(){
? ?? ???returnlist.getFirst();
? ?? ???
? ? }
}

4.7实现队列

public class LinkedListQueue<E> implements Queue<E>{? ?
private class Node{
? ?? ???public E e;
? ?? ???public Node next;
? ?? ???
? ?? ???public Node(E e,Node next){
? ?? ?? ?? ?this.e =e;
? ?? ?? ?? ?this.next =next;
? ?? ???}
? ?? ?? ?public Node(E e)
? ?? ?? ?? ?this(e,null);
? ?? ?? ?? ? public Node(){
? ?? ?? ?? ?? ???this(null,null);
? ?? ?? ?? ? }
? ?? ?? ?? ?
? ?? ?? ?? ? public String toString(){
? ?? ?? ?? ?? ???return e.toreSting();
? ?? ?? ?? ? }
? ?? ???}
? ? private Node head,tail;
? ? private int size;
? ? public LinkListQueue(){
? ?? ???head = null;
? ?? ???tail = null;
? ?? ???size = 0;
? ? }
? ?
? ? public int getSize(){
? ?? ???return size;
? ? }
? ? public boolean isEmpty()
? ? {
? ?? ???return size==0;
? ?? ???
? ? }
? ? public void enqueue(E e){
? ?? ???if (tail ==null){
? ?? ?? ?? ?tail=new Node(e);
? ?? ?? ?? ?head =tail;
? ?? ???}
? ?? ???else{tail.next = new Node(e);
? ?? ?? ?? ?tail = tail.next;}
? ? size++;
? ? }
? ?
? ? }
public E dequeue(){
? ? if(isEmpty()){ //一个合法性的判断
? ?? ???Node retNode = head;
? ?? ???head = head.next;
? ?? ???retNode.next = null;
? ?? ???if(head ==null)
? ?? ?? ?? ?tail=null;
? ?? ???size--;
? ?? ???return retNode.e;
}
}

PS：我是不会说我上周忘了发了，直到刚刚才发现，所以这周懂得都懂。

还有就是目测暑假还有2—3次的样子，之后的话只能说尽量更快一点。

顺带提一嘴，开学之后我可能会开始Java的学习，有兴趣可以看看这个博主，量大高产的那种。

https://blog.csdn.net/qq_53388087