【数据结构】链表及其实现

链表

1.定义及特点

• 链表是一种线性表，由节点构成，每个节点包括数据域和指针域；
• 存储的元素在逻辑上连续，在物理上不连续；
• 链表在插入的时间复杂度为O(1)的，但是查找一个节点或者访问特定编号的节点的时间复杂度为O(n)；

2.优缺点：

• 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
• 但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

3.应用
   常用于构成其他数据结构。如队列、栈。
栈的实现：https://blog.csdn.net/my_miuye/article/details/96424177
队列的实现：https://blog.csdn.net/my_miuye/article/details/96373485

4.实现：（java版）

• 头插法建立链表：新节点插在链表头
• 尾插法建立链表：新节点插在链表尾
• 头插法反转链表：头节点作为新链表的尾节点，将第二个第三个…节点逐个插在尾节点前
• 尾插法反转链表：尾节点作为新链表的头节点，将倒数第二个倒数第三个节点逐个插在头节点后面
• 遍历输出链表

import java.util.Scanner;

public class Node 
{
	public int data;
	public Node next = null;
	
	Node(int data)
	{
		this.data = data;
		this.next = null;	
	}
	//头插法建立链表
	void creatByHead(Scanner reader)
	{
		Node head = null;
		int num = reader.nextInt();
		while(num > 0)
		{
			Node p = new Node(num);
			p.next = head;         //第一次null = null，之后将p指向上一个建立的节点
			head = p;                //将head指向刚建立的节点    
			num = reader.nextInt();
		}
		this.next = head;
	}
	
	//尾插法建立链表
	void creatByTail(Scanner reader)
	{
		Node head = null;
		int num = reader.nextInt();
		while(num > 0)
		{
			Node p = new Node(num);
			if(head == null)
			{
				head = p;
				this.next = head;     //next记录第一个插入的节点
			}
			else
			{
				head.next = p;    //将新创建的节点链在head后
				head = p;        //新节点成为头节点
			}
			num = reader.nextInt();
				
		}
		
	}
	//头插法将链表逆序
	void inversionByHead(Node head)
	{
		if(head == null) return;
		Node p = head;
		head = null;
		while(p!=null)
		{
			Node q = p.next;   //保存p指向的下一个节点后才能将p指向上一个节点
			p.next = head;    //第一次时使第一个节点指向null
			head = p;
			p = q;
		}
		this.next = head;	
	}
	
	//尾插法将链表逆序
	void inversionByTail()
	{
		Node t=null;
		Node q = null;
		Node head=this.next;
		this.next=null;
		while(true)
		{
			Node p = head;
			while(p.next!=null)
			{
				q = p;
				p = p.next;
			}
			q.next = null;
			
			if(this.next==null)
			{
				this.next = p;
				t = p;
			}
			else
			{
				t.next = p;
				t = p;
			}
			if(t == head) break;
		}

	}
	
	//遍历输出
	void traverse()
	{
		Node node = this.next;
		while(node != null)
		{
			System.out.print(node.data+" ");
			node = node.next;
		}
	}
	
}