链表
* 链表由节点组成，节点是由next域连接起来的，每个节点=data+next
* 同时链表在内存中是不连续的。
练习1：单链表的增、删、查、改
* 1）访问某个特定的节点，从头开始去找
* 2）删除、添加某一个特定的节点到某一个位置，只需要找到前一个节点，即可直接添加/删除
* 3）链表是一种内存上不连续的数据结构
class SingleLinekdListTakeHead<E> { protected Node<E> head;//头节点 class Node<E> { protected E data;//数据域 protected Node<E> next;//next引用域 public Node(E data, Node<E> next) { this.data = data; this.next = next; } } //初始化head public SingleLinekdListTakeHead() { head = new Node(new Object(), null); } //在head之后直接插入一个节点，头插法 public void addHead(E element) { Node<E> newNode = new Node(element, null); newNode.next = head.next;//先让新添加的节点的下一个指向原head节点指向的 head.next = newNode;//再让head节点指向新节点 } //尾插法 public void addTail(E element) { Node<E> newNode = new Node(element, null); Node<E> tail = head;//定义一个节点从头走到尾 //tail走到当前链表的尾部 while (tail.next != null) { tail = tail.next; } tail.next = newNode; newNode.next=null; } /** * 固定位置插入一个节点 * 判断参数合法性 * 找到pos位置的前一个节点 * @param pos 固定位置 * @param element 元素 */ public void addPos(int pos, E element) { if (pos <= 0 || pos > getLength()) { return; } Node<E> prev = head.next; int index = 1; while (index++ < pos - 1) { prev = prev.next; } Node<E> newNode = new Node<>(element, null); newNode.next = prev.next; prev.next = newNode; } //删除元素为element的节点 public boolean remove(E element) { //如果只有一个头结点，返回false if (head.next == null) { return false; } //找到该元素所对应的节点 + 该元素所对应的节点的前一个 //从头结点开始遍历 Node<E> tmp = head; while (tmp != null) { if (tmp.next != null && tmp.next.data == element) { //tmp.next是我们要删除的节点 tmp是删除节点的前一个 tmp.next = tmp.next.next; return true; } tmp = tmp.next; } return false; } //设置某个位置的值为newElement public void set(int pos, E newElement){ if(pos <= 0 || pos > getLength()){ return; } //找pos位置的节点 Node<E> tmp = head.next; for(int i=1; i < pos; i++){ tmp = tmp.next; } tmp.data = newElement; } //得到某个元素的值 public E get(E element){ Node<E> tmp = head.next;//从有效节点开始遍历 while(tmp != null){ if(tmp.data == element){ return tmp.data; //找到的话，返回该节点 } tmp = tmp.next; } return null; } //返回长度 public int getLength() { Node<E> tmp = head.next; int length = 0; while (tmp != null) { length++; tmp = tmp.next; } return length; } //打印栈 public String toString() { StringBuilder strs = new StringBuilder(); Node<E> tmp = head.next; while (tmp != null) { strs.append(tmp.data + " "); tmp = tmp.next; } return strs.toString(); //strs是StringBuilder类型，应该添加toString方法，才能返回String类型的 } } public class Linked { public static void main(String[] args) { SingleLinekdListTakeHead<Integer> list=new SingleLinekdListTakeHead(); list.addHead(3); list.addHead(5); list.addHead(8); System.out.println(list.toString());//8 5 3 list.addTail(1); list.addTail(2); list.addTail(4); System.out.println(list.toString());//8 5 3 1 2 4 list.addPos(2, 100); //在2 号位置加入元素100 System.out.println(list.toString()); list.addPos(0, 1000); System.out.println(list.toString()); list.remove(4); System.out.println("删除值为4的元素:"+list.toString()); list.set(2,2);//true,把2号元素的值改为2 System.out.println("把2号元素的值改为2:"+list.toString()); System.out.println(list.get(3)); } }
具体操作的画图分析：
练习2：在链表中开始添加n个元素，将链表逆置输出
public class SingleLinkListExercise { public static <E> void reversePrint(Node<E> head){ if(head == null){ return; } //提取重复的逻辑 reversePrint(head.next); System.out.println(head.data); } public static void main(String[] args) { SingleLinkList<Integer> list = new SingleLinkList<>();
for(int i=0;i<10;i++) {
list.add(i);
}
reversePrint(list.head);
}
}
练习3：双向链表的增加、删除
//双向链表的增加、删除
//双向链表的增加、删除
/**show方法有空指针异常：需要判断当前节点和它的下一个节点是否都为空
* @param <E>
*/
class DoubleLinkList<E>{
protected Node<E> head;
protected Node<E> tail;
class Node<E> {
protected E data;
protected Node<E> prev;
protected Node<E> next;
public Node(E data,Node<E> prev,Node<E> next){
this.data = data;
this.prev = prev;
this.next = next;
}
}
//尾插法
public void add(E data){
Node<E> last=tail;//把目前链表的最后一个节点给last
Node<E> newNode=new Node<>(data,last,null);//创建新节点的前驱是last,后继为null
if(last==null){
head=newNode;
}else {
tail.next=newNode;//让tail指向newNode
}
tail=newNode;//再把newNode赋给新的tail
}
public boolean remove(E data){
if (head==null){
return false;
}
if(head.next==null){
head=null;
tail=null;
return true;
}
//如果删除的是第一个节点
else if(head.data.equals(data)){
head=head.next;
head.prev=null;
return true;
}
//如果删除的是最后一个节点
else if(tail.data.equals(data)){
tail=tail.prev;
tail.next=null;
return true;
}else {
//如果删除的是正常节点
Node<E> prev = head;
Node<E> current = head.next;
while (current != null) {
if (current.data.equals(data)) { //如果当前节点数据是要找的节点
prev.next = current.next; //将前一个的节点的next指向当前节点的下一个
current.next.prev = prev;//当前节点的下一个的前驱指向要删除节点的前一个
current = null; //将要删除的节点置为null
return true;
}
prev = current;//将两个节点继续向下走
current = current.next;
}
}
return false;
}
//打印链表
public void show(){
Node<E> current=head;//定义一个current变量，将head指向current
while ( current!=null &¤t.next!=null){ //需要判断当前节点和下一个都不为空的情况下才能打印链表
System.out.print(current.data+" ");
current= current.next;
}
if(head!=null){ //如果头结点不为空
System.out.print(current.data); //将最后一个节点打印
}else {
System.out.println("当前链表空！！");
}
System.out.println();
}
// public void show(){
// Node<E> current = head;
//
// while(current != null){
// System.out.print(current.data+ " ");
// current = current.next;
// }
// System.out.println();
// }
}
public class DoubleLinkListTest {
public static void main(String[] args) {
DoubleLinkList<Integer> d=new DoubleLinkList<>();
d.add(3);
d.add(4);
d.remove(3);
d.remove(4);
d.show();
// System.out.println(d.remove(3));
// System.out.println(d.remove(5));
// System.out.println(d.remove(7));
// System.out.println(d.remove(10));
// d.show();
//链表为空后，再一次添加时，要求tail也置为null,再从开始添加
for(int i=0;i<4;i++) {
d.add(i+1);
}
d.show();
}
}
练习4：单向循环链表
//不带头节点的单向循环链表 class LoopSingleLinkedList<E>{ protected Node<E> head; class Node<E>{ protected E data; protected Node<E> next; public Node(E data){ this.data = data; } } public void add(E data){ Node<E> newNode=new Node<>(data); //链表为空 if(head == null){ head = newNode; newNode.next = head; } //遍历至尾节点 Node<E> tail = head; while(tail.next != head){ tail = tail.next; } newNode.next = tail.next; tail.next = newNode; } //输出为data的数据 public boolean remove(E data){ //如果头结点为空，返回false if (head == null) { return false; } //这里需要判断，如果当前只有一个节点，则将链表置空，直接删除 if(head.next==head){ head=null; return false; } //如果删除的是头结点，要先找到尾节点，让尾节点指向头结点的下一个 Node<E> tail=head; if (tail.data == data) { while (tail.next != head) { tail=tail.next; } head=head.next; tail.next=head; return true; } //删除正常节点 Node<E> prev = head;//定义一个节点指向头 Node<E> current = head.next;//再定义要删除的结点指向下一个 while(current != head){ if(current.data == data){ prev.next = current.next; current = null; return true; } prev = current; current = current.next; } return false; } //从头结点开始遍历打印，需要定义一个索引指向头结点 public void show(){ Node<E> current=head; while (current!=null&¤t.next!=head){ System.out.print(current.data+" "); current=current.next; } if(head==null){ System.out.println("链表空！"); }else { System.out.println(current.data); } } } public class LoopSingleLinkedListTest { public static void main(String[] args) { LoopSingleLinkedList<Integer> l=new LoopSingleLinkedList(); l.add(3); l.add(4); l.add(5); l.show(); l.remove(3); System.out.println(l.remove(5)); l.remove(4); l.show(); } }
